We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Finding cactus roots in polynomial time.

Golovach, P.A. and Kratsch, D. and Paulusma, D. and Stewart, A. (2016) 'Finding cactus roots in polynomial time.', in Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. Cham, Switzerland: Springer, pp. 361-372. Lecture notes in computer science. (9843).


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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:15 July 2016
Date deposited:03 October 2016
Date of first online publication:09 August 2016
Date first made open access:09 August 2017

Save or Share this output

Look up in GoogleScholar