Fine-Grained Complexity of Regular Path Queries

DOI10.46298/lmcs-19(4:15)2023arXiv2101.01945MaRDI QIDQ6137832

Markus L. Schmid, Katrin Casel

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.01945

zbMATH Keywords

enumerationgraph databasesregular path queriesfine-grained complexity

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items (1)

Shortest distances as enumeration problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expressiveness and static analysis of extended conjunctive regular path queries
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• A trichotomy for regular simple path queries on graphs
• Regular queries on graph databases
• Efficient determination of the transitive closure of a directed graph
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms
• The complexity of regular expressions and property paths in SPARQL
• Fast sparse matrix multiplication
• Querying Graphs with Data
• Evaluation and Enumeration Problems for Regular Path Queries
• Powers of tensors and fast matrix multiplication
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Finding Regular Simple Paths in Graph Databases
• Fine-Grained Complexity Theory (Tutorial)
• On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Multiplying matrices faster than coppersmith-winograd
• Automata, Languages and Programming
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Fine-Grained Complexity of Regular Path Queries