12 citations · 31 across the 16 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012★ 5 cited
Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +1
For an arbitrary undirected simple graph G with m edges, we give an algorithm with running time O(m^4 |L|^2) to generate the set L of all minimal edge dominating sets of G. For bip…
cs.DS2012
A Polynomial kernel for Proper Interval Vertex Deletion
Fedor V. Fomin, Saket Saurabh, Yngve Villanger
It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the p…