Covering Graphs by Simple Circuits

Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael RodehSIAM Journal on Computing 1981 · DOI · OpenReview

Abstract

We show that any biconnected graph with n nodes and m edges can be covered by simple circuits whose total length is at most $\min (3m,m + 6n)$. Our proof suggests an efficient algorithm for finding such a cover.
BibTeX
@article{itai1981covering,
  author = {Alon Itai and Richard J. Lipton and Christos H. Papadimitriou and Michael Rodeh},
  title = {{Covering Graphs by Simple Circuits}},
  journal = {SIAM Journal on Computing},
  year = {1981},
  doi = {10.1137/0210058},
}

Loading related content...

Figure