Golovach, P. and Paulusma, D. and Stewart, I.A. (2013) 'Graph editing to a fixed target.', in Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers. Berlin, Heidelberg: Springer, pp. 192-205. Lecture notes in computer science. (8288).
For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (345Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-45278-9_17|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-45278-9_17|
|Date accepted:||No date available|
|Date deposited:||15 January 2015|
|Date of first online publication:||2013|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|