Berger, Franziska; Gritzmann, Peter; de Vries, Sven Minimum cycle bases for network graphs. (English) Zbl 1082.05083 Algorithmica 40, No. 1, 51-62 (2004). 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|\). Cited in 19 Documents 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 Keywords:Graph cycle; Minimum cycle basis; Matroid; Electrical network PDFBibTeX XMLCite \textit{F. Berger} et al., Algorithmica 40, No. 1, 51--62 (2004; Zbl 1082.05083) Full Text: DOI