Name
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 |V|. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/s00453-004-1098-x | Algorithmica |
Keywords | Field | DocType |
Graph cycle,Minimum cycle basis,Matroid,Electrical network | Matroid,Graph,Discrete mathematics,Electrical network,Combinatorics,Vector space,Multigraph,Cycle basis,Cycle graph,Mathematics,Dense graph | Journal |
Volume | Issue | ISSN |
40 | 1 | 0178-4617 |
Citations | PageRank | References |
33 | 1.81 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franziska Berger | 1 | 44 | 3.25 |
| Peter Gritzmann | 2 | 412 | 46.93 |
| Sven de Vries | 3 | 522 | 58.84 |