Maximum Cycle Packing in Eulerian Graphs Using Local Traces

Peter Recht; Eva-Maria Sprengel

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 1, page 121-132
  • ISSN: 2083-5892

Abstract

top
For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.

How to cite

top

Peter Recht, and Eva-Maria Sprengel. "Maximum Cycle Packing in Eulerian Graphs Using Local Traces." Discussiones Mathematicae Graph Theory 35.1 (2015): 121-132. <http://eudml.org/doc/271227>.

@article{PeterRecht2015,
abstract = {For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.},
author = {Peter Recht, Eva-Maria Sprengel},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge-disjoint cycle packing; local traces; extremal problems in graph theory},
language = {eng},
number = {1},
pages = {121-132},
title = {Maximum Cycle Packing in Eulerian Graphs Using Local Traces},
url = {http://eudml.org/doc/271227},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Peter Recht
AU - Eva-Maria Sprengel
TI - Maximum Cycle Packing in Eulerian Graphs Using Local Traces
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 121
EP - 132
AB - For a graph G = (V,E) and a vertex v ∈ V , let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V . Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.
LA - eng
KW - edge-disjoint cycle packing; local traces; extremal problems in graph theory
UR - http://eudml.org/doc/271227
ER -

References

top
  1. [1] S. Antonakopulos and L. Zhang, Approximation algorithms for grooming in optical network design, Theoret. Comput. Sci. 412 (2011) 3738-3751. doi:10.1016/j.tcs.2011.03.034[Crossref] Zbl1216.68044
  2. [2] F. Bäbler, Über eine spezielle Klasse Euler’scher Graphen, Comment. Math. Helv. 27 (1953) 81-100. doi:10.1007/BF02564555[Crossref] Zbl0050.17905
  3. [3] V. Bafna and P.A. Pevzner, Genome rearrangement and sorting by reversals, SIAM J. Comput. 25 (1996) 272-289. doi:10.1137/S0097539793250627[Crossref] Zbl0844.68123
  4. [4] A. Caprara, Sorting permutations by reversals and Eulerian cycle decompositions, SIAM J. Discrete Math. 12 (1999) 91-110. doi:10.1137/S089548019731994X[Crossref] Zbl0916.68074
  5. [5] A. Caprara, A. Panconesi and R. Rizzi, Packing cycles in undirected Graphs, J. Algorithms 48 (2003) 239-256. doi:10.1016/S0196-6774(03)00052-X[Crossref] Zbl1084.05067
  6. [6] G. Fertin, A. Labarre, I. Rusu, ´E. Tannier and S. Vialette, Combinatorics of Genome Rearrangement (MIT Press, Cambridge, Ma., 2009). Zbl1170.92022
  7. [7] 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. doi:10.1016/j.disc.2009.07.017[WoS][Crossref] Zbl1218.05076
  8. [8] J. Harant, D. Rautenbach, P. Recht, I. Schiermeyer and E.-M. Sprengel, Packing disjoint cycles over vertex cuts, Discrete Math. 310 (2010) 1974-1978. doi:10.1016/j.disc.2010.03.009[Crossref][WoS] Zbl1222.05121
  9. [9] J. Kececioglu and D. Sankoff, Exact and approximation algorithms for sorting by reversals with application to genome rearrangement , Algorithmica 13 (1997) 180-210. doi:10.1007/BF01188586[Crossref] Zbl0831.92014
  10. [10] M. Krivelevich, Z. Nutov, M.R. Salvatpour, J. Yuster and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithm 3(4)) (2007) Article 48. Zbl1297.05127
  11. [11] O. Ore, A problem regarding the tracing of graphs, Elem. Math. 6 (1951) 49-53. Zbl0043.38503
  12. [12] P. Recht and E.-M. Sprengel, Packing Euler graphs with traces, in: Operations Research Proceedings, Klatte, Lüthi and Schmedders (Ed(s)), (Heidelberg, New York, Dordrecht, London, Springer, 2011) 53-58. Zbl1306.05137

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.