Maximum cycle packing using SPR-trees

Christin Otto, Peter Recht

Abstract


Let G = (V, E) be an undirected multigraph without loops. The maximum cycle packing problem is to find a collection Z *  = {C1, ..., Cs} of edge-disjoint cycles Ci subset G of maximum cardinality v(G). In general, this problem is NP-hard. An approximation algorithm for computing v(G) for 2-connected graphs is presented, which is based on splits of G. It essentially uses the representation of the 3-connected components of G by its SPR-tree. It is proved that for generalized series-parallel multigraphs the algorithm is optimal, i.e. it determines a maximum cycle packing Z *  in linear time.


Keywords


maximum cycle packing, decomposition, SPR-trees, edge-disjoint cycle

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.11

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats