• 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 ...
    • 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 ...
    • 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 ...