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).
Abstract
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) |
| Status: | Peer-reviewed |
| 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
| Export: | |
| Look up in GoogleScholar |
