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.; Kratsch, 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. Kratsch

P.T. Lima



Contributors

Hans L. Bodlaender
Editor

Gerhard J. Woeginger
Editor

Abstract

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been dedicated to deciding whether a given graph has a square root that belongs to a particular graph class. There are both polynomial-time solvable and NP-complete cases, depending on the graph class. We contribute with new results in this direction. Given an arbitrary input graph G, we give polynomial-time algorithms to decide whether G has an outerplanar square root, and whether G has a square root that is of pathwidth at most 2.

Citation

Golovach, P., Heggernes, P., Kratsch, D., Lima, P., & Paulusma, D. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In H. L. Bodlaender, & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (275-288). https://doi.org/10.1007/978-3-319-68705-6_21

Conference Name 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017)
Conference Location Eindhoven, The Netherlands
Start Date Jun 21, 2017
End Date Jun 23, 2017
Acceptance Date Jul 31, 2017
Online Publication Date Nov 2, 2017
Publication Date Jun 23, 2017
Deposit Date May 31, 2017
Publicly Available Date Mar 29, 2024
Pages 275-288
Series Title Lecture notes in computer science
Series Number 10520
Series ISSN 0302-9743,1611-3349
Book Title Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers.
ISBN 9783319687049
DOI https://doi.org/10.1007/978-3-319-68705-6_21
Public URL https://durham-repository.worktribe.com/output/1148413

Files





You might also like



Downloadable Citations