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):

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

URL of the conference:

http://www.math.utu.fi/icalp04

URL for downloading the paper:

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
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
11/17/2004 03:58:13 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn178.pdf179.pdf
View attachments here: