LCS Publication Details
Publication Title: COVERING GRAPHS BY SIMPLE CIRCUITS
Publication Author: Itai, Alon
Additional Authors: Lipton, Richard J., Papadimitriou, Christos H. and Rodeh, M.
LCS Document Number: MIT-LCS-TM-155
Publication Date: 2-1-1980
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
A family C1,...,Cm of simple circuits of an undirected multigraph C m (V,E) covers C provided each edge of C is in one of the circuits. The size of such a family is then the sum of the lengths of circuits C1,...,Cm. We are interested here in the question of finding covers of minimum size. Clearly, we can restrict our attention to 2-connected multigraphs : if a graph has a bridge then it has no cover at all.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.