Technical Report CS0104

TR#:CS0104
Class:CS
Title: Covering a Graph by Circuits
Authors: Alon Itai and Michael Rodeh
PDFCS0104.pdf
Abstract: A circuit cover ts a set of circuits which cover all the edges of a graph; Its length ts the sum of the lengths of the circuits. In analyzing irrigation systems and electrical circuits it is necessary to find a short circuit cover. It Is shown ,that every bridge-free connected undirected graph with n vertices and e edges has a circuit cover the length of which Is less than or equal to e+2nlogn. A probabilistic algorithm for flnding such a cover Is presented; Its expected running time Is O(n^2), independent of the input graph. This constitutes one of the first examples of solving a graph-theoretical problem by a probabilistic algorithm -the class of algortihms Introduced by Rabin. If the graph contains two edge-disjoint s-pannlng trees then there exists a circuIt cover of length at most e+n-l. The relationship of the circuit cover problem to the Chinese postman problem is also discussed.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1977/CS/CS0104), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1977
To the main CS technical reports page

Computer science department, Technion
admin