A Unified Approach to Path Problems

DOI10.1145/322261.322272zbMath0462.68041OpenAlexW2010194128MaRDI QIDQ3912034

Robert Endre Tarjan

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322261.322272

zbMATH Keywords

shortest pathgraph algorithmregular expressioncode optimizationsparse systems of linear equationscompilingglobal flow analysis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Iterative numerical methods for linear systems (65F10) Theory of operating systems (68N25) Numerical linear algebra (65F99)

Related Items (29)

Algebraic program analysis ⋮ Functional correctness of C implementations of Dijkstra's, Kruskal's, and Prim's algorithms ⋮ A denotational semantics for low-level probabilistic programs with nondeterminism ⋮ Periodic sets of integers ⋮ Formal language constrained path problems ⋮ Automatizing parametric reasoning on distributed concurrent systems ⋮ Parallel nested dissection for path algebra computations ⋮ Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm ⋮ The complexity of reachability in distributed communicating processes ⋮ Intelligent transportation systems -- Enabling technologies ⋮ Formal Derivation of a High-Trustworthy Generic Algorithmic Program for Solving a Class of Path Problems ⋮ Dijkstra, Floyd and Warshall meet Kleene ⋮ Filter-embedding semiring fusion for programming with MapReduce ⋮ Properties of data flow frameworks: A unified model ⋮ Real-time path planning with limited information for autonomous unmanned air vehicles ⋮ Heuristic least-cost computation of discrete classification functions with uncertain argument values ⋮ Extended transition systems for parametric bisimulation ⋮ Temporal constraint networks ⋮ Automatic verification of distributed systems: the process algebra approach. ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Solving path problems on the GPU ⋮ Indexing Structure for Graph-Structured Data ⋮ Fast and efficient solution of path algebra problems ⋮ Dynamic Programming Algorithms as Products of Weighted Logic Programs ⋮ On legal path problems in digraphs ⋮ A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) ⋮ Heuristic testing procedures for general coherent systems ⋮ Reconstructing sequential behavior from parallel behavior projections ⋮ Regular algebra applied to language problems

This page was built for publication: A Unified Approach to Path Problems