S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
We propose a hierarchical algorithm for approximating shortest paths between all pairs of nodes in a large-scale network. The algorithm begins by extracting a high-level subnetwork of relatively long links (and their associated nodes) where routing decisions are most crucial. This high-level network partitions the shorter links and their nodes into a set of lower-level subnetworks. By fixing gateways within the high-level network for entering and exiting these subnetworks, a computational savings is achieved at the expense of optimality. We explore the magnitude of these tradeoffs between computational savings and associated errors both analytically and empirically with a case study of the Southeast Michigan traffic network. An order-of-magnitude drop in computation times was achieved with an on-line route guidance simulation, at the expense of less than 6% increase in expected trip times. © 1998 INFORMS.
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005
B.K. Boguraev, Mary S. Neff
HICSS 2000
Yao Qi, Raja Das, et al.
ISSTA 2009
Michael D. Moffitt
ICCAD 2009