19 citations · 218 across the 100 of their papers we have counts for
11 papers · 1 filter
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa +2
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is…
Quasi-polynomial-time algorithm for Independent Set in -free graphs via shrinking the space of induced paths
Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in -free graphs, that is, graphs…
Constant Congestion Brambles
Meike Hatzel, Pawel Komosa, Marcin Pilipczuk +1
A bramble in an undirected graph is a family of connected subgraphs of such that for every two subgraphs and in the bramble either $V(H_1) \cap V(H_2) \neq \emp…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Flow-augmentation II: Undirected graphs
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph with distinguished vertices and an intege…
Two lower bounds for -centered colorings
Loïc Dubois, Gwenaël Joret, Guillem Perarnau +2
Given a graph and an integer , a coloring is \emph{-centered} if for every connected subgraph of , either uses more than colors o…