Golovach, P.A. and Paulusma, D. and Stewart, I.A. (2017) 'Graph editing to a fixed target.', Discrete applied mathematics., 216 (Part 1). pp. 181-190.
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.
|Keywords:||Graph editing, Graph containment relation, Computational complexity.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (350Kb)
|Publisher Web site:||https://doi.org/10.1016/j.dam.2014.07.008|
|Publisher statement:||NOTICE: this is the author’s version of a work that was accepted for publication in Discrete applied mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete applied mathematics, 10 January 2017, 216, 181-190, 10.1016/j.dam.2014.07.008|
|Date accepted:||20 July 2014|
|Date deposited:||06 January 2015|
|Date of first online publication:||07 August 2014|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|