P. Golovach
Graph editing to a fixed target
Golovach, P.; Paulusma, D.; Stewart, I. A.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor
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 | Jan 15, 2015 |
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
Accepted Conference Proceeding
(353 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-45278-9_17
You might also like
Using semidirect products of groups to build classes of interconnection networks
(2020)
Journal Article
Variational networks of cube-connected cycles are recursive cubes of rings
(2020)
Journal Article
INRFlow: An interconnection networks research flow-level simulation framework
(2019)
Journal Article
The influence of datacenter usage on symmetry in datacenter network design
(2017)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search