Golovach, P.A. and Kratsch, D. and Stewart, A. and Paulusma, D. (2018) 'Finding cactus roots in polynomial time.', Theory of computing systems., 62 (6). pp. 1409-1426.
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.
Item Type: | Article |
---|---|
Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution. Download PDF (355Kb) |
Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (Advance online version) (564Kb) |
Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (Final published version) (548Kb) |
Status: | Peer-reviewed |
Publisher Web site: | https://doi.org/10.1007/s00224-017-9825-2 |
Publisher 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. |
Date accepted: | 07 November 2017 |
Date deposited: | 15 November 2017 |
Date of first online publication: | 21 November 2017 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |