Fast Algorithms for Solving Path Problems

DOI10.1145/322261.322273zbMath0462.68042OpenAlexW2119179558MaRDI QIDQ3912035

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.322273

zbMATH Keywords

shortest pathgraph algorithmdominatorssparse matrixreducible flow graphregular expressioncode optimizationpath compressioncompilingAckermann's functionglobal flow analysispath expression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (27)

Algebraic program analysis ⋮ Periodic sets of integers ⋮ 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 ⋮ A data structure for arc insertion and regular path finding ⋮ Intelligent transportation systems -- Enabling technologies ⋮ Algebraic Methods Applied to Network Reliability Problems ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Suffix languages in Lr parsing ⋮ Properties of data flow frameworks: A unified model ⋮ Solving Multiple Dataflow Queries Using WPDSs ⋮ Unnamed Item ⋮ Loop Summarization Using Abstract Transformers ⋮ Finite constants: Characterizations of a new decidable set of constants ⋮ Extended transition systems for parametric bisimulation ⋮ Temporal constraint networks ⋮ Constraint preservation through loops ⋮ A SEMANTIC-BASED APPROACH FOR HANDLING INCOMPLETE AND INACCURATE PROVENANCE IN RESERVOIR ENGINEERING ⋮ Loop summarization using state and transition invariants ⋮ Automatic verification of distributed systems: the process algebra approach. ⋮ Partially ordered regular languages for graph queries ⋮ On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection ⋮ Indexing Structure for Graph-Structured Data ⋮ Least-cost partition algorithms ⋮ Fast and efficient solution of path algebra problems

This page was built for publication: Fast Algorithms for Solving Path Problems