Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Mehlhorn, Kurt
Michail, Dimitrios

dblp
dblp



Editor(s):

Nikoletseas, Sotiris

dblp

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

URL of the conference:

http://ru1.cti.gr/wea05/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 02:33:39 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
187.pdf
View attachments here: