Maximum cycle packing using SPR-trees
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
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.11
References
N. Alon, C. McDiarmid, and M. Molloy, Edge-disjoint cycles in regular directed graphs, J. Graph Theory 22 (1996), 231–237.
A. Caprara, A. Panconesi, and R. Rizzi, Packing cycles in undirected graphs, J. Algorithms 48 (2003), 239–256.
M. Chimani, Computing Crossing Numbers, PhD thesis, TU Dortmund (2008). http:// hdl.handle.net/2003/25955
G. Di Battista and R. Tamassia, Incremental planarity testing, 30th Annual Symposium on Foundations of Computer Science (1989), 436–441.
G.Di Battista and R. Tamassia, On-line maintenance of tri connected components with SPQR-trees, Algorithmica 15 (1996), 302–318.
G. Dirac and P. Erdo ̋s, On the maximal number of independent circuits in a graph, Acta Mathematica Academiae Scientiarum Hungarica 14 (1963), 79–94.
P. Erdo ̋s and L. Po ́sa, On the maximal number of disjoint circuits of a graph, Publicationes Mathematicae Debrecen 9 (1962), 3–12.
Z. Friggstad and M.R. Salavatipour, Approximability of packing disjoint cycles, Algorithmica 60 (2011), 395–400.
C. Gutwenger and P. Mutzel, A linear time implementation of SPQR-trees, Proceedings of the 8th International Symposium on Graph Drawing (2000), 77–90.
L. Hao, Edge disjoint cycles in graphs, J. Graph Theory 13 (1989), 313–322.
J. Harant, D. Rautenbach, P. Recht, and F. Regen, Packing edge-disjoint cycles in graphs and the cyclomatic number, Discrete Math. 310 (2010), 1456–1462.
J. Harant, D. Rautenbach, P. Recht, I. Schiermeyer, and E.-M. Sprengel, Packing disjoint cycles over vertex cuts, Discrete Math. 310 (2010), 1974–1978.
N.M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Appl. Math. 54 (1994), 215–217.
M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. Verstraete, and R. Yuster, Approximation al- gorithms and hardness results for cycle packing problems, ACM Transactions on Algorithms (TALG) 3 (2007), 48.
S. Mac Lane, A structural characterization of planar combinatorial graphs, Duke Mathemati- cal Journal 3 (1937), 460–472.
B. Mohar, Obstructions for the disk and the cylinder embedding extension problems, Combi- natorics, Probability and Computing 3 (1994), 375–406.
P. Mutzel, The SPQR-tree data structure in graph drawing, Proceedings of the 30th Interna- tional Conference on Automata, Languages and Programming (2003), 34–46.
D. Rautenbach and F. Regen, On packing shortest cycles in graphs, Information Processing Letters 109 (2009), 816–821.
P. Recht and E.-M. Sprengel, Packing Euler graphs with traces, Operations Research Pro- ceedings 2011 (2012), 53–58.
P. Recht and S. Stehling, On maximum cycle packings in polyhedral graphs, Electron. J. Graph Theory Appl. 2 (1) (2014), 18–31.
W.T. Tutte, Connectivity in graphs (1966).
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.