Skip to main content

Research Repository

Advanced Search

Finding cactus roots in polynomial time

Golovach, P. A.; Kratsch, D.; Paulusma, D.; Stewart, A.

Finding cactus roots in polynomial time Thumbnail


Authors

P. A. Golovach

D. Kratsch

A. Stewart



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





You might also like



Downloadable Citations