Covering Graphs by Simple Circuits
Authors:
- Alon ItaiAIAlon Itai
- Richard J. LiptonRLRichard J. Lipton
- Christos H. PapadimitriouCPChristos H. Papadimitriou
- M. RodehMRM. Rodeh
- Richard J. Lipton Alon ItaiRIRichard J. Lipton Alon Itai
- Carsten ThomassenCTCarsten Thomassen
- Bill JacksonBJBill Jackson
- N. AlonNAN. Alon
- M. TarsiMTM. Tarsi
- 1 November 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 10 (4) , 746-750
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 circuits1978
- 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