MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Cooper, Colin
Frieze, Alan M.
Mehlhorn, Kurt
Priebe, Volker		dblp
dblp
dblp
dblp
Editor(s):
Rolim, Josédblp
BibTeX cite key*:
CooperFriezeMehlhornPriebe97
Title, Booktitle
Title*:
Average-case complexity of shortest-paths problems in the vertex-potential model
Booktitle*:
International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Bologna, Italy
Language:
English
Event Date*
(no longer used):
July 11--12, 1997
Organization:
Event Start Date:
11 July 1997
Event End Date:
12 July 1997
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1269
Number:
Month:
Pages:
15-26
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
3-540-63248-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We study the average-case complexity of shortest-paths problems in the
vertex-potential model. The vertex-potential model is a family of probability distributions on
complete directed graphs with \emph{arbitrary} real edge lengths but
without negative cycles. We show that on a graph with $n$ vertices and
with respect to this model, the single-source shortest-paths problem can be solved in $O(n^2)$
expected time, and the all-pairs shortest-paths problem can be solved in $O(n^2 \log n)$
expected time.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{CooperFriezeMehlhornPriebe97,
AUTHOR = {Cooper, Colin and Frieze, Alan M. and Mehlhorn, Kurt and Priebe, Volker},
 EDITOR = {Rolim, Jos{\'e}},
 TITLE = {Average-case complexity of shortest-paths problems in the vertex-potential model},
 BOOKTITLE = {International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-97)},
 PUBLISHER = {Springer},
 YEAR = {1997},
 VOLUME = {1269},
 PAGES = {15--26},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bologna, Italy},
 ISBN = {3-540-63248-4},
}

Entry last modified by Christine Kiesel, 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)
Volker Priebe		Created
07/14/1997 13:55:30
Revisions
9.
8.
7.
6.
5.		Editor(s)
Christine Kiesel
Christine Kiesel
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
07.09.2006 14:51:45
29.03.2006 14:18:32
04/02/98 03:22:26 PM
03/31/98 11:41:27 AM
03/30/98 06:42:03 PM