| Summary: | <p>Let <span class="math"><em>G</em> = (<em>V</em>, <em>E</em>)</span> be an undirected multigraph without loops. The maximum cycle packing problem is to find a collection <span class="math"><em>Z</em> * = {<em>C</em><sub>1</sub>, ..., <em>C</em><sub><em>s</em></sub>}</span> of edge-disjoint cycles <span class="math"><em>C</em><sub><em>i</em></sub></span> subset <span class="math"><em>G</em></span> of maximum cardinality <span class="math"><em>v</em>(<em>G</em>)</span>. In general, this problem is NP-hard. An approximation algorithm for computing <span class="math"><em>v</em>(<em>G</em>)</span> for 2-connected graphs is presented, which is based on splits of <span class="math"><em>G</em></span>. It essentially uses the representation of the 3-connected components of <span class="math"><em>G</em></span> 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 <span class="math"><em>Z</em> * </span> in linear time.</p>
|
|---|