Skip to main content

Research Repository

Advanced Search

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

Golovach, P.A.; Heggernes, P.; Kratch, D.; Lima, P.T.; Paulusma, D.

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 Thumbnail


Authors

P.A. Golovach

P. Heggernes

D. Kratch

P.T. Lima



Abstract

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class H. There are both polynomial-time solvable and NP-complete results in this direction, depending on H. We present a general framework for the problem if H is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where H is the class of outerplanar graphs and H is the class of graphs of pathwidth at most 2.

Citation

Golovach, P., Heggernes, P., Kratch, D., Lima, P., & Paulusma, D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica, 81(7), 2795-2828. https://doi.org/10.1007/s00453-019-00555-y

Journal Article Type Article
Acceptance Date Feb 22, 2019
Online Publication Date Mar 2, 2019
Publication Date Apr 30, 2019
Deposit Date Feb 22, 2019
Publicly Available Date Mar 2, 2020
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 81
Issue 7
Pages 2795-2828
DOI https://doi.org/10.1007/s00453-019-00555-y
Public URL https://durham-repository.worktribe.com/output/1307495

Files





You might also like



Downloadable Citations