Covering Graphs by Simple Circuits

DOI10.1137/0210058MaRDI QIDQ3922184zbMATH OpenOpenAlexFDO

Authors Alon Itai, Richard J. Lipton, Michael Rodeh, Christos Papadimitriou

Publication date 1981

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0210058

zbMATH Keywords

edge connectivityEulerian subgraphsgraph algorithms

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(22)

• Nowhere zero flow and circuit covering in regular matroids
• On shortest cocycle covers of graphs
• The multi-tree approach to reliability in distributed networks
• Short cycle covers and the cycle double cover conjecture
• A parallel algorithm for approximating the minimum cycle cover
• Some properties of the fleet assignment problem
• Extensions of flow theorems
• Covering a graph with cycles.
• Proofs of two minimum circuit cover conjectures
• Routing problems: A bibliography
• An overview of graph covering and partitioning
• A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs
• A bound on the total size of a cut cover
• A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface
• Circuit covers of signed graphs
• Covering the edges of a graph by circuits
• Covering Multigraphs by Simple Circuits
• Minimum \(T\)-joins and signed-circuit covering
• Postman tours and cycle covers
• Computation of minimal event bases that ensure diagnosability
• Shortest coverings of graphs with cycles
• Shipper collaboration

This page was built for publication: Covering Graphs by Simple Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922184)