Enumeration for FO Queries over Nowhere Dense Graphs

DOI10.1145/3517035OpenAlexW4300618478MaRDI QIDQ5889796

Luc Segoufin, Nicole Schweikardt, Alexandre Vigny

Publication date: 27 April 2023

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3517035

zbMATH Keywords

query evaluationsparse graphsconstant-delay enumeration

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (3)

Enumeration for FO Queries over Nowhere Dense Graphs ⋮ Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries ⋮ Unnamed Item

Cites Work

• Elements of finite model theory.
• Generalized model-checking over locally tree-decomposable classes
• The complexity of first-order and monadic second-order logic revisited
• On nowhere dense graphs
• Domination Problems in Nowhere-Dense Classes
• Enumeration of monadic second-order queries on trees
• Storing a sparse table
• Deciding first-order properties of locally tree-decomposable structures
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• Deciding First-Order Properties of Nowhere Dense Graphs
• First order properties on nowhere dense structures
• Answering FO+MOD Queries under Updates on Bounded Degree Databases
• First-order queries on structures of bounded degree are computable with constant delay
• The succinctness of first-order logic on linear orders
• Enumeration for FO Queries over Nowhere Dense Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Enumeration for FO Queries over Nowhere Dense Graphs