Browsing Bergen Open Research Archive by Author "Thilikos, Dimitrios M."

Now showing items 1-10 of 10

    • An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL 

      Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020)
      In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ...

    • An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL 

      Fomin, Fedor; Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex deletion, edge deletion, edge contraction, or ...

    • Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs 

      Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some ...

    • Clustering to Given Connectivities 

      Golovach, Petr; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2019)
      We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and ...

    • Combing a Linkage in an Annulus 

      Golovach, Petr; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      A linkage in a graph 𝐺 of size 𝑘 is a subgraph 𝐿 of 𝐺 whose connected components are 𝑘 paths. The pattern of a linkage of size 𝑘 is the set of 𝑘 pairs formed by the endpoints of these paths. A consequence of the ...

    • Compound Logics for Modification Problems 

      Fomin, Fedor; Golovach, Petr; Sau, Ignasi; Stamoulis, Giannos; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with ...

    • Dynamic Programming on Bipartite Tree Decompositions 

      Jaffke, Lars; Morelle, Laure; Sau, Ignasi; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of ...

    • A Note on Exact Algorithms for Vertex Ordering Problems on Graphs 

      Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M.C.A.; Kratsch, Dieter; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2011-01-21)
      In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling ...

    • Subgraph Complementation 

      Fomin, Fedor; Golovach, Petr; Strømme, Torstein J. F.; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2020-02)
      A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ...

    • Variants of plane diameter completion 

      Golovach, Petr; Requile, Clement; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2015)
      The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the ...