This item is provided by the institution :
Technological Educational Institute of Athens
Repository :
Ypatia - Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2000 (EN)
Improved algorithms for dynamic shortest paths (EN)

Ζαρολιάγκης, Χρήστος (EL)
Πάντζιου, Γραμματή Ε. (EL)
Djidjev, H.N. (EN)

Τεχνολογικό Εκπαιδευτικό Ίδρυμα Αθήνας. Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε. (EL)

We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n-vertex digraphs of genus O(n1−ε) for any ε>0. (EN)

journalArticle

Open Shortest Path First (Computer network protocol) (EN)
Dynamic algorithm (EN)
Δυναμικός αλγόριθμος (EN)
Συντομότερη διαδρομή (EN)
Planar digraph (EN)
Επίπεδα διγράμματος (EN)

ΤΕΙ Αθήνας (EL)
Technological Educational Institute of Athens (EN)

Algorithmica (EN)

English

2000

DOI: 10.1.1.423.4896

Springer-Verlag (EN)



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)