Article Per Year (5 Year)
p-Index From 2021 - 2026
0
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Peter Recht
Operations Research and Business Informatics, TU Dortmund, 44221 Dortmund, Germany
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Maximum cycle packing using SPR-trees Christin Otto; Peter Recht
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 7, No 1 (2019): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2019.7.1.11

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.
Co-Authors Christin Otto