On-line and dynamic algorithms for shortest path problems | Zendy

Hristo Djidjev | Zendy; Grammati Pantziou | Zendy; Christos Zaroliagis | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On-line and dynamic algorithms for shortest path problems

Author(s) -

Hristo Djidjev,

Grammati Pantziou,

Christos Zaroliagis

Publication year - 1995

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/3-540-59042-0_73

Subject(s) - shortest path problem , computer science , digraph , k shortest path routing , algorithm , shortest path faster algorithm , sublinear function , exploit , yen's algorithm , enhanced data rates for gsm evolution , line (geometry) , path (computing) , floyd–warshall algorithm , graph , theoretical computer science , dijkstra's algorithm , mathematics , discrete mathematics , artificial intelligence , geometry , computer security , programming language

We describe algorithms for finding shortest paths and distances in a planar digraph which 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. Our data structures can be updated after any such change in only polylogarithmic time, while a single-pair query is answered in sublinear time. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research