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		dblp
dblp
dblp
Not MPG Author(s):
Kavitha, Telikepalli
Editor(s):
Thomas, Wolfgang
Weil, Pascal		dblp
dblp
Not MPII Editor(s):
Thomas, Wolfgang
Weil, Pascal
BibTeX cite key*:
KMM07
Title, Booktitle
Title*:
New Approximation Algorithms for Minimum Cycle Bases of Graphs
Mehlhorn_2007_a_m.pdf (462.28 KB)
Booktitle*:
STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science
Event, URLs
Conference URL::
http://www-i7.informatik.rwth-aachen.de/stacs07/
Downloading URL:
http://www.springerlink.com/content/740w28k651vx26l8/fulltext.pdf
Event Address*:
Aachen, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
22 February 2007
Event End Date:
24 February 2007
Publisher
Name*:
Springer
URL:
http://www.springer.com
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4393
Number:
Month:
February
Pages:
512-523
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
978-3-540-70917-6; 3-540-70917-7
Sequence Number:
DOI:
10.1007/978-3-540-70918-3_44
Note, Abstract, ©
(LaTeX) Abstract:

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_2$generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction.

We present two new algorithms to compute an approximate minimum cycle basis. For any integer k ≥ 1, we give (2k − 1)-approximation algorithms with expected running time O(k m n1 + 2/k + m n(1 + 1/k)(ω − 1)) and deterministic running time O( n3 + 2/k ), respectively. Here ω is the best exponent of matrix multiplication. It is presently known that ω < 2.376. Both algorithms are o( mω) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Θ(mω) bound.
We also present a 2-approximation algorithm with $O(m^{\omega}\sqrt{n\log n})$expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n3) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

URL for the Abstract:
http://www.springerlink.com/content/740w28k651vx26l8/
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{KMM07,
AUTHOR = {Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios},
 EDITOR = {Thomas, Wolfgang and Weil, Pascal},
 TITLE = {New Approximation Algorithms for Minimum Cycle Bases of Graphs},
 BOOKTITLE = {STACS 2007 : 24th Annual Symposium on Theoretical Aspects of Computer Science},
 PUBLISHER = {Springer},
 YEAR = {2007},
 VOLUME = {4393},
 PAGES = {512--523},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Aachen, Germany},
 MONTH = {February},
 ISBN = {978-3-540-70917-6},
; ISBN = {3-540-70917-7},
 DOI = {10.1007/978-3-540-70918-3_44},
}

Entry last modified by Anja Becker, 02/28/2008
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
02/26/2007 12:24:42
Revisions
7.
6.
5.
4.
3.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
06.02.2008 09:50:27
21.06.2007 17:18:16
19.06.2007 14:54:21
19.06.2007 14:48:30
04.06.2007 16:13:56