Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Finding cactus roots in polynomial time.

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:
Export
Look up in GoogleScholar