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

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

URL of the conference:


URL for downloading the paper:

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
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)
Christine Kiesel
Created
08/14/2006 12:50:56 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_2006_a_m.pdf
View attachments here: