I'm interested in the following problem.

Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j = \varnothing$), such that each $C_i$ forms a simple cycle in $G$ and $k$ is maximum possible.

In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.

Is this problem well-known? Is there a known approach to solve it?


This paper may be helpful with regard to the question you raised: https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.