Finding cactus roots in polynomial time

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

doi:10.1007/s00224-017-9825-2

Finding cactus roots in polynomial time

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

Authors

P.A. Golovach

D. Kratsch

A. Stewart

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Abstract

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class H is called the H-SQUARE ROOT problem. By showing boundedness of treewidth we prove that SQUARE ROOT is polynomial-time solvable on some classes of graphs with small clique number and that H-SQUARE ROOT is polynomial-time solvable when H is the class of cactuses.

Citation

Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2

Journal Article Type	Article
Acceptance Date	Nov 7, 2017
Online Publication Date	Nov 21, 2017
Publication Date	Aug 1, 2018
Deposit Date	Nov 15, 2017
Publicly Available Date	Nov 15, 2017
Journal	Theory of Computing Systems
Print ISSN	1432-4350
Electronic ISSN	1433-0490
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	62
Issue	6
Pages	1409-1426
DOI	https://doi.org/10.1007/s00224-017-9825-2
Public URL	https://durham-repository.worktribe.com/output/1371227

Files

Accepted Journal Article (363 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.