On the public citation graph

Dichotomies for Evaluating Simple Regular Path Queries

0 signed · 58 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/net.3230140403openalex-snapshot
The even‐path problem for graphs and digraphs
inferredcites →https://doi.org/10.1007/978-3-540-27836-8_21openalex-snapshot
Approximating Longest Directed Paths and Cycles
inferredcites →https://doi.org/10.1007/978-3-540-28629-5_70openalex-snapshot
Complexity of Decision Problems for Simple Regular Expressions
inferredcites →https://doi.org/10.1007/978-3-540-73420-8_33openalex-snapshot
Parameterized Approximability of the Disjoint Cycle Problem
inferredcites →https://doi.org/10.1007/978-3-662-53536-3_6openalex-snapshot
Finding Two Edge-Disjoint Paths with Length Constraints
inferredcites →https://doi.org/10.1016/0022-0000(80)90057-4openalex-snapshot
The subgraph homeomorphism problem
inferredcites →https://doi.org/10.1016/0304-3975(80)90009-2openalex-snapshot
The directed subgraph homeomorphism problem
inferredcites →https://doi.org/10.1016/0304-3975(94)00097-3openalex-snapshot
Fixed-parameter tractability and completeness II: On completeness for W[1]
inferredcites →https://doi.org/10.1016/j.tcs.2009.03.018openalex-snapshot
Efficient enumeration of words in regular languages
inferredcites →https://doi.org/10.1016/s0304-0208(08)73110-4openalex-snapshot
How to Find Long Paths Efficiently
inferredcites →https://doi.org/10.1093/jigpal/jzv028openalex-snapshot
Relative expressive power of navigational querying on graphs using transitive closure
inferredcites →https://doi.org/10.1109/c-m.1977.217812openalex-snapshot
International Conference on Very Large Data Bases
inferredcites →https://doi.org/10.1109/ccc.2007.21openalex-snapshot
On Parameterized Path and Chordless Path Problems
inferredcites →https://doi.org/10.1137/0208032openalex-snapshot
The Complexity of Enumeration and Reliability Problems
inferredcites →https://doi.org/10.1137/s0097539703427203openalex-snapshot
The Parameterized Complexity of Counting Problems
inferredcites →https://doi.org/10.1137/s009753979122370xopenalex-snapshot
Finding Regular Simple Paths in Graph Databases
inferredcites →https://doi.org/10.1137/s0097539792228228openalex-snapshot
Fixed-Parameter Tractability and Completeness I: Basic Results
inferredcites →https://doi.org/10.1145/1017074.1017095openalex-snapshot
DTDs versus XML schema
inferredcites →https://doi.org/10.1145/1060745.1060848openalex-snapshot
Expressiveness of XSDs
inferredcites →https://doi.org/10.1145/1735886.1735890openalex-snapshot
Inference of concise regular expressions and DTDs
inferredcites →https://doi.org/10.1145/210332.210337openalex-snapshot
Color-coding
inferredcites →https://doi.org/10.1145/2187836.2187922openalex-snapshot
Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard
inferredcites →https://doi.org/10.1145/2448496.2448526openalex-snapshot
Extracting minimum-weight tree patterns from a schema with neighborhood constraints
inferredcites →https://doi.org/10.1145/2463664.2467795openalex-snapshot
A trichotomy for regular simple path queries on graphs
inferredcites →https://doi.org/10.1145/2494529openalex-snapshot
The complexity of regular expressions and property paths in SPARQL
inferredcites →https://doi.org/10.1145/2850413openalex-snapshot
Querying Graphs with Data
inferredcites →https://doi.org/10.1145/2886094openalex-snapshot
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
inferredcites →https://doi.org/10.1145/298514.298576openalex-snapshot
Graph-theoretic methods in database theory
inferredcites →https://doi.org/10.1145/3104031openalex-snapshot
Foundations of Modern Query Languages for Graph Databases
inferredcites →https://doi.org/10.1145/3105960openalex-snapshot
BonXai
inferredcites →https://doi.org/10.1145/3183713.3190654openalex-snapshot
G-CORE
inferredcites →https://doi.org/10.1145/321239.321249openalex-snapshot
Derivatives of Regular Expressions
inferredcites →https://doi.org/10.1145/321707.321712openalex-snapshot
Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N 3 Additions and N 3 Comparisons
inferredcites →https://doi.org/10.1145/322047.322048openalex-snapshot
Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
inferredcites →https://doi.org/10.1145/3308558.3313472openalex-snapshot
Navigating the Maze of Wikidata Query Logs
inferredcites →https://doi.org/10.1287/mnsc.17.11.712openalex-snapshot
Finding the K Shortest Loopless Paths in a Network
inferredcites →https://doi.org/10.1287/mnsc.18.7.401openalex-snapshot
A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
inferredcites →https://doi.org/10.1287/opre.16.3.682openalex-snapshot
Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
inferredcites →https://doi.org/10.14778/3402707.3402739openalex-snapshot
Optimizing and parallelizing ranked enumeration
inferredcites →https://doi.org/10.4230/lipics.swat.2016.12openalex-snapshot
Lower Bounds for Approximation Schemes for Closest String
inferredcites →https://doi.org/10.5860/choice.35-6287openalex-snapshot
The algorithm design manual

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-51466-2_28openalex-snapshot
Formal Languages in Information Extraction and Graph Databases
inferred← citeshttps://doi.org/10.1007/978-3-031-77850-6_8openalex-snapshot
PathFinder: Returning Paths in Graph Queries
inferred← citeshttps://doi.org/10.1109/access.2024.3371976openalex-snapshot
Path Querying in Graph Databases: A Systematic Mapping Study
inferred← citeshttps://doi.org/10.1145/3371316.3371319openalex-snapshot
Bridging Theory and Practice with Query Log Analysis
inferred← citeshttps://doi.org/10.1145/3422648.3422661openalex-snapshot
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
inferred← citeshttps://doi.org/10.1145/3448016.3457545openalex-snapshot
Querying in the Age of Graph Databases and Knowledge Graphs
inferred← citeshttps://doi.org/10.1145/3448016.3457561openalex-snapshot
PG-Keys: Keys for Property Graphs
inferred← citeshttps://doi.org/10.1145/3514230openalex-snapshot
Conjunctive Regular Path Queries with Capture Groups
inferred← citeshttps://doi.org/10.1145/3517804.3524149openalex-snapshot
The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs
inferred← citeshttps://doi.org/10.1145/3517804.3526066openalex-snapshot
Towards Theory for Real-World Data
inferred← citeshttps://doi.org/10.1145/3584372.3588664openalex-snapshot
Conjunctive Regular Path Queries under Injective Semantics
inferred← citeshttps://doi.org/10.1145/3722234.3725822openalex-snapshot
Querying Graph Data: Where We Are and Where To Go
inferred← citeshttps://doi.org/10.1145/3725242openalex-snapshot
Output-Sensitive Evaluation of Regular Path Queries
inferred← citeshttps://doi.org/10.1145/3802033openalex-snapshot
cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries
inferred← citeshttps://doi.org/10.14778/3587136.3587151openalex-snapshot
Representing Paths in Graph Database Pattern Matching
inferred← citeshttps://doi.org/10.46298/lmcs-19(4:15)2023openalex-snapshot
Fine-Grained Complexity of Regular Path Queries
inferred← citeshttps://doi.org/10.46298/lmcs-19(4:20)2023openalex-snapshot
A Trichotomy for Regular Trail Queries
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.