Browsing Bergen Open Research Archive by Author "Thilikos, Dimitrios M."
Now showing items 110 of 10

An Algorithmic MetaTheorem 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 MetaTheorem 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 nvertex 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 modeltheoretic 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, 20110121)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, 202002)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 ...