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 | Aug 9, 2017 |
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
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
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(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