8 citations · 39 across the 15 of their papers we have counts for
23 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,…
The treewidth and pathwidth of graph unions
Bogdan Alecu, Vadim Lozin, Daniel A. Quiroz +3
Given two -vertex graphs and of bounded treewidth, is there an -vertex graph of bounded treewidth having subgraphs isomorphic to and ? Our main res…
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…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
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…
CoBe -- Coded Beacons for Localization, Object Tracking, and SLAM Augmentation
Roman Rabinovich, Ibrahim Jubran, Aaron Wetzler +1
This paper presents a novel beacon light coding protocol, which enables fast and accurate identification of the beacons in an image. The protocol is provably robust to a predefined…
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…
Parity Games, Imperfect Information and Structural Complexity
Bernd Puchala, Roman Rabinovich
We address the problem of solving parity games with imperfect information on finite graphs of bounded structural complexity. It is a major open problem whether parity games with pe…
Distributed Domination on Graph Classes of Bounded Expansion
Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich +1
We provide a new constant factor approximation algorithm for the (connected) distance- dominating set problem on graph classes of bounded expansion. Classes of bounded expansion…
Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion
Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3
A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…
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…
Routing with Congestion in Acyclic Digraphs
Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx +1
We study the version of the -disjoint paths problem where demand pairs , , are specified in the input and the paths in the solution are allowed…
On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor
Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz +2
The generalised colouring numbers and were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have sin…
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…
The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
Felix Canavoi, Erich Grädel, Roman Rabinovich
For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time. However, it has…
Down the Borel Hierarchy: Solving Muller Games via Safety Games
Daniel Neider, Roman Rabinovich, Martin Zimmermann
We transform a Muller game with n vertices into a safety game with (n!)^3 vertices whose solution allows to determine the winning regions of the Muller game and to compute a finite…
Graph Searching, Parity Games and Imperfect Information
Bernd Puchala, Roman Rabinovich
We investigate the interrelation between graph searching games and games with imperfect information. As key consequence we obtain that parity games with bounded imperfect informati…