A Unified Approach to Path Problems

Research output: Contribution to journalArticle

155 Scopus citations

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 languageEnglish (US)
Pages (from-to)577-593
Number of pages17
JournalJournal of the ACM (JACM)
Volume28
Issue number3
DOIs
StatePublished - Jul 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A Unified Approach to Path Problems'. Together they form a unique fingerprint.

  • Cite this