Finding Regular Simple Paths in Graph Databases

DOI10.1137/S009753979122370XzbMath0845.68033OpenAlexW2135282325MaRDI QIDQ4862795

Alberto O. Mendelzon, Peter T. Wood

Publication date: 15 September 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979122370x

zbMATH Keywords

NP-completenesssimple pathlabelled directed graph

Mathematics Subject Classification ID

Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-Viral Infection Patterns ⋮ Formal language constrained path problems ⋮ Labeled cuts in graphs ⋮ Labeled shortest paths in digraphs with negative and positive edge weights ⋮ Evaluation and Enumeration Problems for Regular Path Queries ⋮ Algebraic rewritings for optimizing regular path queries. ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Regular languages with variables on graphs ⋮ Foundations of graph path query languages. Course notes for the reasoning web summer school 2021 ⋮ A Trichotomy for Regular Trail Queries ⋮ Navigational and Rule-Based Languages for Graph Databases ⋮ Federation and Navigation in SPARQL 1.1 ⋮ Graph Grammars for Querying Graph-like Data ⋮ Querying incomplete information in semistructured data ⋮ Partially ordered regular languages for graph queries ⋮ A trichotomy for regular simple path queries on graphs ⋮ Weighted path queries on semistructured databases ⋮ Regular path queries under approximate semantics ⋮ Bounded regular path queries in view-based data integration ⋮ Path querying on acyclic graphs using Boolean grammars ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Fault-tolerant computation of distributed regular path queries ⋮ Foundations of RDF Databases ⋮ Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks ⋮ User-Constrained Multimodal Route Planning ⋮ Unnamed Item ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Queries and computation on the web ⋮ Unnamed Item ⋮ Graph indexing for spatial data traversal in road map databases ⋮ Regular path queries with constraints ⋮ Formal languages in information extraction and graph databases ⋮ Regular expressions for data words