# An exact algorithm for the statistical shortest path problem

Liang Deng, M. D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

9 Citations (Scopus)

## Abstract

Graph algorithms are widely used in VLSI CAD. Traditional graph algorithms can handle graphs with deterministic edge weights. As VLSI technology continues to scale into nanometer designs, we need to use probability distributions for edge weights in order to model uncertainty due to parameter variations. In this paper, we consider the statistical shortest path (SSP) problem. Given a graph G, the edge weights of G are random variables. For each path P in G, let L/sub P/ be its length, which is the sum of all edge weights on P. Clearly L/sub P/ is a random variable and we let /spl mu//sub P/, and /spl omega//sub P//sup 3/ be its mean and variance, respectively. In the SSP problem, our goal is to find a path P connecting two given vertices to minimize the cost function /spl mu//sub p/, + /spl Phi/ (/spl omega//sub P//sup 2/) where /spl Phi/ is an arbitrary function. (For example, if /spl Phi/ (/spl times/) /spl equiv/ the cost function is /spl mu//sub P/, + 3/spl omega//sub P/.) To minimize uncertainty in the final result, it is meaningful to look for paths with bounded variance, i.e., /spl omega//sub P//sup 2/ /spl les/ B for a given fixed bound B. In this paper, we present an exact algorithm to solve the SSP problem in O(B(V + E)) time where V and E are the numbers of vertices and edges, respectively, in G. Our algorithm is superior to previous algorithms for SSP problem because we can handle: 1) general graphs (unlike previous works applicable only to directed acyclic graphs), 2) arbitrary edge-weight distributions (unlike previous algorithms designed only for specific distributions such as Gaussian), and 3) general cost function (none of the previous algorithms can even handle the cost function /spl mu//sub P/, + 3/spl omega//sub P/. Finally, we discuss applications of the SSP problem to maze routing, buffer insertions, and timing analysis under parameter variations.
Original language English Proceedings of The 11th Asia and South Pacific Conference on Design Automation, ASP-DAC 2006 IEEE 6 9780780394513, 0780394518 Published - 27 Jan 2006 11th Asia and South Pacific Design Automation Conference, ASP-DAC 2006 - Pacifico Yokohama, Yokohama, JapanDuration: 24 Jan 2006 → 27 Jan 2006https://www.aspdac.com/aspdac2006/ (Conference website)https://www.aspdac.com/aspdac2006/tpc/pdf/finalprogprint_nosign.pdf (Conference programme )https://ieeexplore.ieee.org/xpl/conhome/10626/proceeding (Conference proceedings)

### Publication series

Name Proceedings of The Asia and South Pacific Conference on Design Automation, ASP-DAC 2006

### Conference

Conference 11th Asia and South Pacific Design Automation Conference, ASP-DAC 2006 Japan Yokohama 24/01/06 → 27/01/06 https://www.aspdac.com/aspdac2006/ (Conference website)https://www.aspdac.com/aspdac2006/tpc/pdf/finalprogprint_nosign.pdf (Conference programme )https://ieeexplore.ieee.org/xpl/conhome/10626/proceeding (Conference proceedings)

## Fingerprint

Dive into the research topics of 'An exact algorithm for the statistical shortest path problem'. Together they form a unique fingerprint.