MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kavitha, Telikepalli
Mehlhorn, Kurt
Michail, Dimitrios
Paluch, Katarzyna		dblp
dblp
dblp
dblp
Not MPG Author(s):
Paluch, Katarzyna
Editor(s):
Díaz, Josep
Karhumäki, Juhani
Lepistö, Arto
Sannella, Donald		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Diaz, Josep
Karhumäki, Juhani
Lepistö, Arto
Sannella, Donald
BibTeX cite key*:
KMMP2004c
Title, Booktitle
Title*:
A Faster Algorithm for Minimum Cycle Basis of Graphs
179.pdf (258.64 KB); Mehlhorn178.pdf (199.65 KB)
Booktitle*:
Automata, languages and programming : 31st International Colloquium, ICALP 2004
Event, URLs
Conference URL::
http://www.math.utu.fi/icalp04
Downloading URL:
http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3142&spage=846
Event Address*:
Turku, Finland
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
12 July 2004
Event End Date:
16 July 2004
Publisher
Name*:
Springer
URL:
http://www.springeronline.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3142
Number:
Month:
July
Pages:
846-857
Year*:
2004
VG Wort Pages:
ISBN/ISSN:
0302-9743
Sequence Number:
DOI:
10.1007/b99859
Note, Abstract, ©
(LaTeX) Abstract:
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result for this problem was an $O(m^{\omega}n)$ algorithm, where $\omega$ is the best exponent of matrix multiplication. It is presently known that $\omega < 2.376$.
We obtain an $O(m^2n + mn^2\log n)$ algorithm for this problem. Our algorithm also uses fast matrix multiplication.
When the edge weights are integers, we have an $O(m^2n)$ algorithm.
For unweighted graphs which are reasonably dense, our
algorithm runs in $O(m^{\omega})$ time. For any $\epsilon > 0$,
we also design a $1+\epsilon$ approximation algorithm to compute a cycle basis which is at most $1+\epsilon$ times the weight of a minimum cycle basis. The running time of this algorithm is $O(\frac{m^{\omega}}{\epsilon}\log(W/{\epsilon}))$ for
reasonably dense graphs, where $W$ is the largest edge weight.
URL for the Abstract:
http://springerlink.metapress.com/content/w22rj36g2xmuwfmf/?p=6f06fcd3bbb44b259a7e6eccd4b84030&pi=70
HyperLinks / References / URLs:
http://dblp.uni-trier.de/db/conf/icalp/icalp2004.html#KavithaMMP04
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{KMMP2004c,
AUTHOR = {Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios and Paluch, Katarzyna},
 EDITOR = {D{\'i}az, Josep and Karhum{\"a}ki, Juhani and Lepist{\"o}, Arto and Sannella, Donald},
 TITLE = {A Faster Algorithm for Minimum Cycle Basis of Graphs},
 BOOKTITLE = {Automata, languages and programming : 31st International Colloquium, ICALP 2004},
 PUBLISHER = {Springer},
 YEAR = {2004},
 VOLUME = {3142},
 PAGES = {846--857},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Turku, Finland},
 MONTH = {July},
 ISBN = {0302-9743},
 DOI = {10.1007/b99859},
}

Entry last modified by Anja Becker, 03/02/2010
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
11/17/2004 15:58:13
Revisions
10.
9.
8.
7.
6.		Editor(s)
Anja Becker
Dimitrios Michail
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
05.02.2008 13:54:34
03/02/2007 01:19:42 PM
04.10.2006 08:01:29
29.09.2006 09:29:50
13.06.2006 12:33:16