Skip to main content
added the cycle tag
Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76
Source Link
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges

given a biconnected symmetric graph with weighted edges,
what is the algorithmic complexity of determining a set of pairwise edge-disjoint cycles with maximal sum of edge weights if there are no other constraints besides edge-disjointness of the cycles and maximal weightsum of their edges?

Determing such a set of cycles is a stepping stone in an algorithm for determining a heaviest euler tour in complete symmetric graphs with $n=2k$ vertices (which isn't eulerian), which in turn would yield an improved heuristic for the non-eulerian windy postman problem.