Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Shortest paths in digraphs of small treewidth. Part I, Sequential algorithms

MPG-Autoren
/persons/resource/persons44233

Chaudhuri,  Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Chaudhuri, S., & Zaroliagis, C. (2000). Shortest paths in digraphs of small treewidth. Part I, Sequential algorithms. Algorithmica, 27(3/4), 212-226.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-33FD-6
Zusammenfassung
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.