25 citations · 79 across the 15 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
math.CO2019★ 1 cited
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2
Let , and , respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph . One can a…
cs.DS2019
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
math.CO2019★ 25 cited
Clique-Width for Hereditary Graph Classes
Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma
Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class is bounded by a constant,…