Computing Cycle Covers without Short Cycles

Markus Bläser, Bodo SiebertESA 2001 · OpenReview

Abstract

A cycle cover of a graph is a spanning subgraph where each node is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. We call the decision problems whether a directed or undirected graph has a k-cycle cover k-DCC and k-UCC. Given a graph with edge weights one and two, Min-k-DCC and Min-k-UCC are the minimization problems of finding a k-cycle cover with minimum weight.
BibTeX
@inproceedings{blaser2001computing,
  author = {Markus Bläser and Bodo Siebert},
  title = {{Computing Cycle Covers without Short Cycles}},
  booktitle = {ESA},
  year = {2001},
  url = {https://openreview.net/forum?id=T3W6Z2vJiH},
}

Loading related content...

Figure