A Unified Approach to Path Problems.

Abstract

We describe a general method for solving path problems on directed graphs. Such path problems include finding shortest paths, solving sparse systems of linear equations, and carrying out global flow analysis of computer programs. Our method consists of two steps. First, we construct a collection of regular expressions representing sets of paths in the graph. This can be done by using any standard algorithm, such as Gaussian or Gauss-Jordon elimination. Next, we apply a natural mapping from regular expressions into the given problem domain. We exhibit the mappings required to find shortest paths, solve sparse systems of linear equations, and carry out global flow analysis. Our results provide a general-purpose algorithm for solving any path problem, and show that the problem of constructing path expressions is in some sense the most general path problem. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1979
Accession Number
ADA068229

Entities

People

  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Automata
  • Computer Programs
  • Computer Science
  • Computers
  • Continuity
  • Elimination
  • Equations
  • High Level Languages
  • Linear Algebra
  • Linear Algebraic Equations
  • New York
  • Real Numbers
  • Software Development
  • Theorems
  • United States

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.