Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Mehlhorn, Kurt
Priebe, Volker

dblp
dblp



BibTeX cite key*:

MehlhornPriebe97

Title

Title*:

On the All-Pairs Shortest-Path Algorithm of Moffat and Takaoka

Journal

Journal Title*:

Random Structures Algorithms

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, pp, Date

Volume*:

10

Number:

1/2

Publishing Date:

1997

Pages*:

205-220

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We review how to solve the all-pairs shortest-path problem in a non-negatively weighted digraph with $n$ vertices in expected time $O(n^2 \log n)$. This bound is shown to hold with high probability for a wide class of probability distributions on non-negatively weighted digraphs. We also prove that for a large class of probability distributions, $\Omega(n\log n)$ time is necessary with high probability to compute shortest-path distances with respect to a single source.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

http://dblp.uni-trier.de/db/journals/rsa/rsa10.html#MehlhornP97
http://dblp.uni-trier.de/rec/bibtex/journals/rsa/MehlhornP97

Copyright Message:


Personal Comments:


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:

@ARTICLE{MehlhornPriebe97,
AUTHOR = {Mehlhorn, Kurt and Priebe, Volker},
TITLE = {On the All-Pairs Shortest-Path Algorithm of {Moffat} and {Takaoka}},
JOURNAL = {Random Structures Algorithms},
YEAR = {1997},
NUMBER = {1/2},
VOLUME = {10},
PAGES = {205--220},
}


Entry last modified by Christine Kiesel, 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)
Volker Priebe
Created
04/02/1997 06:29:01 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Uwe Brahm
Volker Priebe
Volker Priebe
Edit Dates
28.08.2006 10:23:27
04/06/98 05:22:27 PM
02/04/97 17:38:00
02/04/97 17:29:01
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section