An ADD-Based Algorithm for Shortest Path Back-Tracing of Large Graphs

R. I. Bahar, G. D. Hachtel, E. Macii, A. Pardo, M. Poncino and F. Somenzi

VLSI Great Lakes Symposium, March 1994

Abstract

Symbolic computation techniques play a fundamental role in these days logic synthesis and formal hardware verification algorithms. Recently, Algebraic Decision Diagrams, i.e., BDD's with a set of constant values different than the set {0,1}, have been used to solve general purpose problems, such as matrix multiplication, shortest path calculation, and solution of linear systems, as well as logic synthesis and formal verification problems, such as timing analysis, re-synthesis for low-power, probabilistic analysis of FSM's, and state space decomposition for approximate FSM traversal. ADD-based procedures for single-source and all-pairs shortest path weight calculation have appeared to be very effective for the manipulation of large graphs (over 1027 vertices and 1036 edges). However, for those procedures to be applicable to real problems, for example flow network problems, computing only shortest path weights is not enough; what it is needed is an algorithm that, given the weight of a shortest path between two vertices of a graph, actually determines the sequence of vertices belonging to the shortest path. In this paper, we propose a symbolic algorithm for shortest path back-tracing which exploits the compactness of the ADD data structure to handle large graphs.

Click here to download the compressed postscript version.

BibTeX Entry

@InProceedings{Bahar94,
        ADDRESS = "University of Notre Dame, IN" ,
        AUTHOR = "R. I. Bahar and G. D. Hachtel and E. Macii and A. Pardo and M. Poncino and F. Somenzi" ,
        BOOKTITLE = "VLSI Great Lakes Symposium" ,
        MONTH =   mar  ,
        PAGES = "248-251" ,
        TITLE = "An {ADD}-Based Algorithm for Shortest Path Back-Tracing of Large Graphs" ,
        YEAR = "1994"
        }
Return to the home page