8 citations · 39 across the 15 of their papers we have counts for
9 papers · 1 filter
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
Rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk +2
We study two notions of being well-structured for classes of graphs that are inspired by classic model theory. A class of graphs is monadically stable if it is impossible to de…
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich +2
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary f…
Algorithmic Properties of Sparse Digraphs
Stephan Kreutzer, Patrice Ossona de Mendez, Roman Rabinovich +1
The notions of bounded expansion and nowhere denseness have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expan…
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer +4
We prove that whenever is a graph from a nowhere dense graph class , and is a subset of vertices of , then the number of subsets of that are realized as…
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz
Nowhere dense classes of graphs are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a character…
The Generalised Colouring Numbers on Classes of Bounded Expansion
Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich +1
The generalised colouring numbers , , and were introduced by Kierstead and Yang as generalisations of the usual colouring…
DAG-width is PSPACE-complete
Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich
Berwanger et al. show that for every graph of size and DAG-width there is a DAG decomposition of width and size . This gives a polynomial time algorithm f…
Directed Width Measures and Monotonicity of Directed Graph Searching
Łukasz Kaiser, Stephan Kreutzer, Roman Rabinovich +1
We consider generalisations of tree width to directed graphs, that attracted much attention in the last fifteen years. About their relative strength with respect to "bounded width…