8 citations · 66 across the 52 of their papers we have counts for
5 papers · 1 filter
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…
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan +1
In a reconfiguration version of an optimization problem the input is an instance of and two feasible solutions and . The objective is to determin…
Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
Sebastian Siebertz
The notion of nowhere dense graph classes was introduced by Nešetřil and Ossona de Mendez and provides a robust concept of uniform sparseness of graph classes. Nowhere dense classe…
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…
Parameterized Distributed Complexity Theory: A logical approach
Sebastian Siebertz, Alexandre Vigny
Parameterized complexity theory offers a framework for a refined analysis of hard algorithmic problems. Instead of expressing the running time of an algorithm as a function of the…