ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Alles auswählen Exportieren

Digitale Medien

Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms (2000)

Chaudhuri, S. ; Zaroliagis, C. D.

Springer

Algorithmica 27 (2000), S. 212-226

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1432-0541

Schlagwort(e): Key words. Shortest path, Graph theory, Treewidth, Dynamic algorithm.

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik , Mathematik

Notizen: Abstract. We consider the problem of preprocessing an n -vertex digraph with real edge weights so that subsequent queries for the shortest path or distance between any two vertices can be efficiently answered. We give algorithms that depend on the treewidth of the input graph. When the treewidth is a constant, our algorithms can answer distance queries in O(α(n)) time after O(n) preprocessing. This improves upon previously known results for the same problem. We also give a dynamic algorithm which, after a change in an edge weight, updates the data structure in time O(n β ) , for any constant 0 〈 β 〈 1 . Furthermore, an algorithm of independent interest is given: computing a shortest path tree, or finding a negative cycle in linear time.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/s004530010016

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer