MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Hariharan, Ramesh
Telikepalli, Kavitha
Mehlhorn, Kurt		dblp
dblp
dblp
Not MPG Author(s):
Hariharan, Ramesh
Telikepalli, Kavitha
Editor(s):
Bugliesi, Michele
Preneel, Bart
Sassone, Vladimir
Wegener, Ingo		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Bugliesi, Michele
Preneel, Bart
Sassone, Vladimir
Wegener, Ingo
BibTeX cite key*:
HTM06a
Title, Booktitle
Title*:
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
Mehlhorn_2006_a_m.pdf (230.64 KB)
Booktitle*:
Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/m663785210782002/fulltext.pdf
Event Address*:
Venice, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 July 2006
Event End Date:
14 July 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4051
Number:
Month:
Pages:
250-261
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
3-540-35904-4
Sequence Number:
DOI:
10.1007/11786986_23
Note, Abstract, ©
(LaTeX) Abstract:
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A {–1,0,1} edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get -1. The vector space over generated by these vectors is the cycle space of G. A minimum cycle basis is a set of cycles of minimum weight that span the cycle space of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in time (where ω< 2.376 is the exponent of matrix multiplication). Here we present an O(m3n + m2n2logn) algorithm. We also slightly improve the running time of the current fastest randomized algorithm from O(m2nlogn) to O(m2 n + mn2 logn).
URL for the Abstract:
http://www.springerlink.com/content/m663785210782002/?p=deff85ef4a5141b98004f0d5164ff1af&pi=0
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{HTM06a,
AUTHOR = {Hariharan, Ramesh and Telikepalli, Kavitha and Mehlhorn, Kurt},
 EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimir and Wegener, Ingo},
 TITLE = {A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs},
 BOOKTITLE = {Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {4051},
 PAGES = {250--261},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Venice, Italy},
 ISBN = {3-540-35904-4},
 DOI = {10.1007/11786986_23},
}

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)
Christine Kiesel		Created
08/14/2006 12:50:56
Revisions
13.
12.
11.
10.
9.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Uwe Brahm
Uwe Brahm		Edit Dates
05.02.2008 15:59:56
04.06.2007 16:27:29
04.06.2007 16:26:35
2007-04-26 18:54:59
08.03.2007 14:37:38