Edge cycle cover
From Wikipedia, the free encyclopedia
In graph theory, a branch of mathematics, an edge cycle cover (sometimes called simply cycle cover[1]) of a graph is a family of cycles which are subgraphs of G and contain all edges of G.
If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. In this case, the set of the cycles constitutes a spanning subgraph of G.
If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover.
Minimum-Weight Cycle Cover
For a weighted graph, the Minimum-Weight Cycle Cover Problem (MWCCP) is the problem to find a cycle cover with minimal sum of weights of edges in all cycles of the cover.
For bridgeless planar graphs, the MWCCP can be solved in polynomial time.[2]
