Now showing items 1-10 of 10

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

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

(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 ﻿

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