Formal language constrained path problems

DOI10.1007/BFB0054371MaRDI QIDQ5054859zbMATH OpenFDO

Authors Riko Jacob, Chris L. Barrett, Madhav V. Marathe

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054371

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Formal-Language-Constrained Path Problems
• Evaluation and enumeration problems for regular path queries
• Engineering Label-Constrained Shortest-Path Algorithms
• Engineering label-constrained shortest-path algorithms
• A trichotomy for regular simple path queries on graphs

Cites work

• A generalization of Dijkstra's algorithm
• A Unified Approach to Path Problems
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Approximation Schemes for the Restricted Shortest Path Problem
• Easy problems for tree-decomposable graphs
• Finding Regular Simple Paths in Graph Databases
• scientific article; zbMATH DE number 432747 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length

Cited in

(8)

• The shortest kinship description problem
• A trichotomy for regular simple path queries on graphs
• Path querying with conjunctive grammars by matrix multiplication
• Engineering label-constrained shortest-path algorithms
• Formal-Language-Constrained Path Problems
• scientific article; zbMATH DE number 1405617 (Why is no real title available?)
• Nodes connected by path languages
• Formal Derivation of a High-Trustworthy Generic Algorithmic Program for Solving a Class of Path Problems

This page was built for publication: Formal language constrained path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5054859)