A trichotomy for regular simple path queries on graphs
type: Item
instance of: scholarly article
title: A trichotomy for regular simple path queries on graphs
zbMATH Open document ID: 1436.68131
author: Guillaume Bagan
author: Angela Bonifati
author: Benoît Groz
published in: Journal of Computer and System Sciences
publication date: 2019-11-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/1212.6857
full work available at URL: jcss19 (1).pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7138703
zbMATH Keywords: graphs
zbMATH Keywords: regular simple paths
zbMATH Keywords: complexity
zbMATH Keywords: regular languages
zbMATH Keywords: automata
MaRDI profile type: Publication
OpenAlex ID: W4390689069
arXiv ID: 1212.6857
cites work: Color-coding
cites work: Modularity of cycles and paths in graphs
cites work: Formal-Language-Constrained Path Problems
cites work: Q4198056
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q4227581
cites work: Directed tree-width
cites work: The even-path problem for graphs and digraphs
cites work: The complexity of regular expressions and property paths in SPARQL
cites work: Evaluation and Enumeration Problems for Regular Path Queries
cites work: Finding Regular Simple Paths in Graph Databases
cites work: Finding an Even Simple Path in a Directed Planar Graph
cites work: A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
cites work: Q4298260
cites work: The Theory of Definite Automata
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Finding k Disjoint Paths in a Directed Planar Graph
cites work: On finite monoids having only trivial subgroups
cites work: Complexity results on labeled shortest path problems from wireless routing metrics
Wikidata QID: Q127214244
DOI: 10.1016/J.JCSS.2019.08.006
description: scientific article