P. A. Golovach
Finding cactus roots in polynomial time
Golovach, P. A.; Kratsch, D.; Paulusma, D.; Stewart, A.
Authors
Contributors
Veli Mäkinen
Editor
Simon J. Puglisi
Editor
Leena Salmela
Editor
Abstract
A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show that it is possible to test in O(n4)O(n4) time whether an n-vertex graph G has a cactus root.
Citation
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Finding cactus roots in polynomial time. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (361-372). https://doi.org/10.1007/978-3-319-44543-4_28
Conference Name | 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). |
---|---|
Conference Location | Helsinki, Finland |
Start Date | Aug 17, 2016 |
End Date | Aug 19, 2016 |
Acceptance Date | Jul 15, 2016 |
Online Publication Date | Aug 9, 2016 |
Publication Date | Aug 9, 2016 |
Deposit Date | Oct 1, 2016 |
Publicly Available Date | Mar 29, 2024 |
Pages | 361-372 |
Series Title | Lecture notes in computer science |
Series Number | 9843 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. |
ISBN | 9783319445427 |
DOI | https://doi.org/10.1007/978-3-319-44543-4_28 |
Public URL | https://durham-repository.worktribe.com/output/1149728 |
Files
Accepted Conference Proceeding
(305 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-44543-4_28
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