Abstract
A general method is described for solving path problems on directed graphs. Such path problems include finding shortest paths, solving sparse systems of hnear equaUons, and carrying out global flow analysis of computer programs The method consists of two steps First, a collecUon of regular expressions representmg sets of paths m the graph Is constructed This can be done by using any standard algorithm, such as Gaussmn or Gauss-Jordan elimination. Next, a natural mapping from regular expressions into the gwen problem domain is applied. The mappmgs required to find shortest paths are exhibited, sparse systems of hnear equations are solved, and global flow analysis Is carned out. The results provide a general-purpose algonthm for solwng any path problem and show that the problem of constructing path expressions is in some sense the most general path problem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 577-593 |
| Number of pages | 17 |
| Journal | Journal of the ACM (JACM) |
| Volume | 28 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jul 1 1981 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Artificial Intelligence
- Information Systems
- Control and Systems Engineering
- Hardware and Architecture
Keywords
- Ganss-Jordan ehmmatlon
- Gaussian elmamation
- code optimization
- compiling
- global flow analysis
- graph algorithm
- linear algebra
- path problem
- regular expression
- semdattlce
- shortest path
- sparse matrix