User: Guest  Login
Document type:
Zeitschriftenaufsatz 
Author(s):
Berger, F.; P. Gritzmann and S. de Vries 
Title:
Minimum cycle bases for network graphs 
Abstract:
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|2log |V|}) with a space requirement of Θ(|E|2). This method is especially suitable for large sparse graphs of electric engineering applications since there, typically, |E| is close to linear in...    »
 
Keywords:
Graph cycle, Minimum cycle, basis Matroid, Electrical network 
Journal title:
Algorithmica 
Year:
2004 
Journal issue:
40 
Pages contribution:
51-62 
Reviewed:
ja 
Language:
en 
TUM Institution:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik