Article citationsMore>>

Harant, J., Rautenbach, D., Recht, P. and Regen, F. (2010.) Packing Edge-Disjoint Cycles in Graphs and the Cyclomatic Number. Discrete Mathematics, 310, 1456-1462,
http://dx.doi.org/10.1016/j.disc.2009.07.017

has been cited by the following article:

• TITLE: A Dynamic Programming Approach for the Max-Min Cycle Packing Problem in Even Graphs

  AUTHORS: Peter Recht

  KEYWORDS: Maximum Edge-Disjoint Cycle Packing, Extremal Problems in Graph Theory, Dynamic Programming, -Shortest Path Procedure

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.6 No.4, October 28, 2016

  ABSTRACT: Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles Ciin G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.