The directed grid theorem
K Kawarabayashi, S Kreutzer - Proceedings of the forty-seventh annual …, 2015 - dl.acm.org
The grid theorem, originally proved in 1986 by Robertson and Seymour in Graph Minors V,
is one of the most central results in the study of graph minors. It has found numerous …
is one of the most central results in the study of graph minors. It has found numerous …
Congestion-free rerouting of flows on dags
Changing a given configuration in a graph into another one is known as a re-configuration
problem. Such problems have recently received much interest in the context of algorithmic …
problem. Such problems have recently received much interest in the context of algorithmic …
Directed tangle tree-decompositions and applications∗
The tangle tree-decomposition theorem, proved by Robertson and Seymour in their seminal
graph minors series, turns out to be an extremely valuable tool in structural and algorithmic …
graph minors series, turns out to be an extremely valuable tool in structural and algorithmic …
The power of cut-based parameters for computing edge-disjoint paths
R Ganian, S Ordyniak - Algorithmica, 2021 - Springer
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an
undirected graph G and a set of terminal pairs P and asks whether G contains a set of …
undirected graph G and a set of terminal pairs P and asks whether G contains a set of …
Kernels for the disjoint paths problem on subclasses of chordal graphs
J Chaudhary, H Gahlawat, M Włodarczyk… - arXiv preprint arXiv …, 2023 - arxiv.org
Given an undirected graph $ G $ and a multiset of $ k $ terminal pairs $\mathcal {X} $, the
Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $ G …
Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $ G …
On structural parameterizations of the edge disjoint paths problem
In this paper we revisit the classical edge disjoint paths (EDP) problem, where one is given
an undirected graph G and a set of terminal pairs P and asks whether G contains a set of …
an undirected graph G and a set of terminal pairs P and asks whether G contains a set of …
A local-to-global theorem for congested shortest paths
Amiri and Wargalla (2020) proved the following local-to-global theorem in directed acyclic
graphs (DAGs): if $ G $ is a weighted DAG such that for each subset $ S $ of 3 nodes there …
graphs (DAGs): if $ G $ is a weighted DAG such that for each subset $ S $ of 3 nodes there …
Polynomial planar directed grid theorem
The grid theorem, originally proved by Robertson and Seymour in 1986 [RS10, Graph
Minors V], is one of the most central results in the study of graph minors and has found many …
Minors V], is one of the most central results in the study of graph minors and has found many …
The all-or-nothing flow problem in directed graphs with symmetric demand pairs
We study the approximability of the All-or-Nothing multicommodity flow problem in directed
graphs with symmetric demand pairs (SymANF). The input consists of a directed graph …
graphs with symmetric demand pairs (SymANF). The input consists of a directed graph …
Digraphs of bounded width
S Kreutzer, O Kwon - Classes of Directed Graphs, 2018 - Springer
Structural parameters for undirected graphs such as the path-width or tree-width of graphs
have played a crucial role in developing a structure theory for graphs based on the minor …
have played a crucial role in developing a structure theory for graphs based on the minor …