4 citations · 4 across the 5 of their papers we have counts for
12 papers
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…
Linear rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich +1
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the…
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich +1
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between…
Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs
Meike Hatzel, Roman Rabinovich, Sebastian Wiederrecht
A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based…
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…