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.
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.
|Full text:||(AM) Accepted Manuscript|
Download PDF (430Kb)
|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
|Look up in GoogleScholar|