MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mehlhorn, Kurt
Michail, Dimitrios		dblp
dblp
Editor(s):
Nikoletseas, Sotirisdblp
Not MPII Editor(s):
Nikoletseas, Sotiris
BibTeX cite key*:
MM05
Title, Booktitle
Title*:
Implementing Minimum Cycle Basis Algorithms
187.pdf (150.71 KB)
Booktitle*:
Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005
Event, URLs
Conference URL::
http://ru1.cti.gr/wea05/
Downloading URL:
http://dx.doi.org/10.1007/11427186_5
http://www.mpi-sb.mpg.de/~michail/papers/implMCB.ps.gz
Event Address*:
Santorini, Greece
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 May 2005
Event End Date:
13 May 2005
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3503
Number:
Month:
May
Pages:
32-43
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
3-540-25920-1
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph $G = (V,E)$ with $n$ vertices and $m$ edges. We describe an efficient implementation of an $O(m^3 + mn^2\log n)$ algorithm presented in~\cite{PINA95}. For sparse graphs this is the currently best known algorithm.
This algorithm's running time can be partitioned into two parts
with time $O(m^3)$ and $O( m^2n + mn^2 \log n)$ respectively.
Our experimental findings imply that the true bottleneck of a
sophisticated implementation is the $O( m^2 n + mn^2 \log n)$ part. A straightforward implementation would require $\Omega(nm)$ shortest path computations, thus we develop several heuristics in order to get a practical algorithm. Our experiments show that in random graphs our techniques result in a significant speedup.

Based on our experimental observations, we combine the two fundamentally different approaches to compute a minimum cycle basis used in~\cite{PINA95,KMMP04} and~\cite{HOR87,MATR02}, to obtain a new hybrid algorithm with running time
$O( m^2 n^2 )$. The hybrid algorithm is very efficient in practice for random dense unweighted graphs.

Finally, we compare these two algorithms with a number of previous implementations for finding a minimum cycle basis in an undirected graph.
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/wea/wea2005.html#MehlhornM05
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MM05,
AUTHOR = {Mehlhorn, Kurt and Michail, Dimitrios},
 EDITOR = {Nikoletseas, Sotiris},
 TITLE = {Implementing Minimum Cycle Basis Algorithms},
 BOOKTITLE = {Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005},
 PUBLISHER = {Springer},
 YEAR = {2005},
 VOLUME = {3503},
 PAGES = {32--43},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Santorini, Greece},
 MONTH = {May},
 ISBN = {3-540-25920-1},
}

Entry last modified by Christine Kiesel, 09/29/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Dimitrios Michail		Created
03/30/2005 14:33:39
Revisions
6.
5.
4.
3.
2.		Editor(s)
Christine Kiesel
Tamara Hausmann
Christine Kiesel
Dimitrios Michail
Dimitrios Michail		Edit Dates
29.09.2006 09:24:49
13.06.2006 12:05:11
03.11.2005 16:47:05
05/24/2005 02:09:47 PM
03/30/2005 02:38:18 PM