Parallel algorithms for solving aggregated shortest-path problems

Authors
Romeijn, HE Smith, RL
Citation
He. Romeijn et Rl. Smith, Parallel algorithms for solving aggregated shortest-path problems, COMPUT OPER, 26(10-11), 1999, pp. 941-953
Citations number
10
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
26
Issue
10-11
Year of publication
1999
Pages
941 - 953
Database
ISI
SICI code
0305-0548(199909)26:10-11<941:PAFSAS>2.0.ZU;2-9
Abstract
We consider the problem of computing in parallel all pairs of shortest path s in a general large-scale directed network of N nodes. A hierarchical netw ork decomposition algorithm is provided that yields for an important subcla ss of problems log N savings in computation time over the traditional paral lel implementation of Dijkstra's algorithm. Error bounds are provided for t he procedure and are illustrated numerically for a problem motivated by int elligent transportation systems.