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).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (299Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-319-44543-4_28 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-44543-4_28 |
| 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
| Export: | |
| Look up in GoogleScholar |
