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

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

URL of the conference:

http://www-i7.informatik.rwth-aachen.de/stacs07/

URL for downloading the paper:

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
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
02/26/2007 12:24:42 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_2007_a_m.pdf
View attachments here: