P.A. Golovach
Finding cactus roots in polynomial time
Golovach, P.A.; Kratsch, D.; Stewart, A.; Paulusma, D.
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.
Published Journal Article (Advance online version)
(577 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Advance online version
Published Journal Article (Final published version)
(561 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Final published version
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search