Finding cactus roots in polynomial time

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

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, August). Finding cactus roots in polynomial time. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 27th International Workshop on Combinatorial Algorithms (IWOCA 2016).
• 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
• Print ISSN: 0302-9743
• 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