×

Minimum cycle bases for network graphs. (English) Zbl 1082.05083

Summary: The minimum cycle basis problem in a graph \(G = (V,E)\) is the task to construct a minimum length basis of its cycle vector space. A well-known algorithm by Horton of 1987 needs running time \(O(|V||E|2.376)\). We present a new combinatorial approach which generates minimum cycle bases in time \(O(\max\{|E|3,|E||V|2\log |V|\})\) with a space requirement of \(\Theta(|E|2)\). This method is especially suitable for large sparse graphs of electric engineering applications since there, typically, \(|E|\) is close to linear in \(|V|\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05B35 Combinatorial aspects of matroids and geometric lattices
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI