Skip to main content

Research Repository

Advanced Search

Graph editing to a fixed target

Golovach, P.; Paulusma, D.; Stewart, I. A.

Graph editing to a fixed target Thumbnail


Authors

P. Golovach



Contributors

T. Lecroq
Editor

L. Mouchard
Editor

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.

Citation

Golovach, P., Paulusma, D., & Stewart, I. A. (2013). Graph editing to a fixed target. In T. Lecroq, & L. Mouchard (Eds.), Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers (192-205). https://doi.org/10.1007/978-3-642-45278-9_17

Conference Name International Workshop on Combinatorial Algorithms
Conference Location Rouen, France
Publication Date Jan 1, 2013
Deposit Date Jun 27, 2013
Publicly Available Date Mar 29, 2024
Pages 192-205
Series Title Lecture notes in computer science
Series Number 8288
Series ISSN 0302-9743,1611-3349
Book Title Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers.
ISBN 9783642452772
DOI https://doi.org/10.1007/978-3-642-45278-9_17
Public URL https://durham-repository.worktribe.com/output/1156284

Files





You might also like



Downloadable Citations