Maximum cycle packing using SPR-trees
<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> * = {...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2019-04-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/346 |
| _version_ | 1811250721488633856 |
|---|---|
| author | Christin Otto Peter Recht |
| author_facet | Christin Otto Peter Recht |
| author_sort | Christin Otto |
| collection | DOAJ |
| description | <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> |
| first_indexed | 2024-04-12T16:08:52Z |
| format | Article |
| id | doaj.art-59a79b57886d4c6aadabc3e87916ce3a |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:08:52Z |
| publishDate | 2019-04-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-59a79b57886d4c6aadabc3e87916ce3a2022-12-22T03:25:57ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872019-04-017110.5614/ejgta.2019.7.1.11142Maximum cycle packing using SPR-treesChristin Otto0Peter Recht1Operations Research and Business Informatics, TU Dortmund, 44221 Dortmund, GermanyOperations Research and Business Informatics, TU Dortmund, 44221 Dortmund, Germany<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>https://www.ejgta.org/index.php/ejgta/article/view/346maximum cycle packing, decomposition, spr-trees, edge-disjoint cycle |
| spellingShingle | Christin Otto Peter Recht Maximum cycle packing using SPR-trees Electronic Journal of Graph Theory and Applications maximum cycle packing, decomposition, spr-trees, edge-disjoint cycle |
| title | Maximum cycle packing using SPR-trees |
| title_full | Maximum cycle packing using SPR-trees |
| title_fullStr | Maximum cycle packing using SPR-trees |
| title_full_unstemmed | Maximum cycle packing using SPR-trees |
| title_short | Maximum cycle packing using SPR-trees |
| title_sort | maximum cycle packing using spr trees |
| topic | maximum cycle packing, decomposition, spr-trees, edge-disjoint cycle |
| url | https://www.ejgta.org/index.php/ejgta/article/view/346 |
| work_keys_str_mv | AT christinotto maximumcyclepackingusingsprtrees AT peterrecht maximumcyclepackingusingsprtrees |