Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 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

 (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},