Evaluation and Enumeration Problems for Regular Path Queries
From MaRDI portal
Publication:3305367
DOI10.4230/LIPIcs.ICDT.2018.19zbMath1489.68081arXiv1710.02317OpenAlexW2792264844MaRDI QIDQ3305367
Publication date: 6 August 2020
Full work available at URL: https://arxiv.org/abs/1710.02317
Database theory (68P15) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (5)
Unnamed Item ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Unnamed Item ⋮ A trichotomy for regular simple path queries on graphs ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Efficient enumeration of words in regular languages
- The directed subgraph homeomorphism problem
- The complexity of regular expressions and property paths in SPARQL
- Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
- Querying Graphs with Data
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Finding Two Edge-Disjoint Paths with Length Constraints
- The even-path problem for graphs and digraphs
- Color-coding
- Relative expressive power of navigational querying on graphs using transitive closure
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Finding Regular Simple Paths in Graph Databases
- Parameterized Approximability of the Disjoint Cycle Problem
- Automata, Languages and Programming
- Parameterized Algorithms
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Finding the K Shortest Loopless Paths in a Network
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
This page was built for publication: Evaluation and Enumeration Problems for Regular Path Queries
