Random walks in a supply network

Haifeng Qian, Sani R. Nassif, Sachin S. Sapatnekar

Research output: Contribution to journalConference articlepeer-review

136 Scopus citations


This paper presents a power grid analyzer based on a random walk technique. A linear-time algorithm is first demonstrated for DC analysis, and is then extended to perform transient analysis. The method has the desirable property of localizing computation, so that it shows massive benefits over conventional methods when only a small part of the grid is to be analyzed (for example, when the effects of small changes to the grid are to be examined). Even for the full analysis of the grid, experimental results show that the method is faster than existing approaches and has an acceptable error margin. This method has been applied to test circuits of up to 2.3M nodes. For example, for a circuit with 70K nodes, the solution time for a single node was 0.42 sec and the complete solution was obtained in 17.6 sec.

Original languageEnglish (US)
Pages (from-to)93-98
Number of pages6
JournalProceedings - Design Automation Conference
StatePublished - 2003
EventProceedings of the 40th Design Automation Conference - Anaheim, CA, United States
Duration: Jun 2 2003Jun 6 2003


  • Power grid
  • Random walk


Dive into the research topics of 'Random walks in a supply network'. Together they form a unique fingerprint.

Cite this