Covering Graphs by Simple Circuits
- 1 November 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 10 (4) , 746-750
- https://doi.org/10.1137/0210058
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.
Keywords
This publication has 6 references indexed in Scilit:
- Edge-disjoint branching in directed multigraphsInformation Processing Letters, 1979
- On the eulericity of a graphJournal of Graph Theory, 1978
- Covering a graph by circuitsPublished by Springer Nature ,1978
- A good algorithm for edge-disjoint branchingInformation Processing Letters, 1974
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- Minimum partition of a matroid into independent subsetsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965