R. Rabinovich

activity

20112026

most citedOn the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor

8 citations · 39 across the 15 of their papers we have counts for

collaborators

Showing 2014Show all

2 papers · 1 filter

cs.DM2014

DAG-width is PSPACE-complete

Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich

Berwanger et al. show that for every graph $G$ of size $n$ and DAG-width $k$ there is a DAG decomposition of width $k$ and size $n^{O (k)}$ . This gives a polynomial time algorithm f…

cs.DM2014★ 4 cited

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…