Covering Graphs by Simple Circuits
Lists
Only you see this
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...