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:

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

Golovach, P.A. and Heggernes, P. and Kratch, D. and Lima, P.T. and Paulusma, D. (2019) 'Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2.', Algorithmica., 81 (7). pp. 2795-2828.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(430Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/s00453-019-00555-y
Publisher statement:This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-019-00555-y
Date accepted:22 February 2019
Date deposited:22 February 2019
Date of first online publication:02 March 2019
Date first made open access:02 March 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar