Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time

Baswana, S., Goyal, V., & Sen, S. (2005). All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time. In STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science (pp. 666-679). Berlin, Germany: Springer.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
stacs05.ps (beliebiger Volltext), 263KB
 
Datei-Permalink:
-
Name:
stacs05.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Baswana, Surender1, Autor           
Goyal, Vishrut, Autor
Sen, Sandeep1, Autor           
Diekert, Volker, Herausgeber
Durand, Bruno, Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Let $G=(V,E)$ be an unweighted undirected graph on $n$ vertices. Let $\delta(u,v)$ denote the distance between vertices $u,v\inV$. An algorithm is said to compute all-pairs $t$-approximate shortest -paths/distances, for some $t\ge 1$, if for each pair of vertices $u,v\in V$, the path/distance reported by the algorithm is not longer/greater than $t\delta(u,v)$.\\ This paper presents two randomized algorithms for computing all-pairs nearly 2-approximate shortest distances. The first algorithm takes expected $O(m^{2/3}n\log n + n^2)$ time, and for any $u,v\in V$ reports distance no greater than $2\delta(u,v)+1$. Our second algorithm requires expected $O(n^2\log^{3/2} n)$ time, and for any $u,v\in V$, reports distance bounded by $2\delta(u,v) + 3$.\\ This paper also presents the first expected $O(n^2)$ time algorithm to compute all-pairs 3-approximate distances.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-08-012005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 279196
Anderer: Local-ID: C1256428004B93B8-CDE770BF7CC4479FC1256FBE0037715A-BGS2005
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Stuttgart, Germany
Start-/Enddatum: 2005-03-08

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: STACS 2005 : 22nd Annual Symposium on Theoretical Aspects of Computer Science
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 666 - 679 Identifikator: ISBN: 3-540-24998-2

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 3404 Artikelnummer: - Start- / Endseite: - Identifikator: -