Deciding first-order properties of locally tree-decomposable structures
From MaRDI portal
Publication:3196630
DOI10.1145/504794.504798zbMath1323.03014arXivcs/0004007OpenAlexW1993920925WikidataQ127770703 ScholiaQ127770703MaRDI QIDQ3196630
Publication date: 30 October 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0004007
first-order logicplanar graphsmodel checkinglocalityquery evaluationtree-widthparameterized complexity
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07)
Related Items
On finding short resolution refutations and small unsatisfiable subsets, Characterising bounded expansion by neighbourhood complexity, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Enumeration for FO Queries over Nowhere Dense Graphs, A Retrospective on (Meta) Kernelization, The complexity of first-order and monadic second-order logic revisited, An existential locality theorem, FO model checking on geometric graphs, On the complexity of connection games, A Basic Parameterized Complexity Primer, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, Quickly deciding minor-closed parameters in general graphs, Polynomial time approximation schemes and parameterized complexity, Junction Tree Factored Particle Inference Algorithm for Multi-Agent Dynamic Influence Diagrams, Fixed-parameter tractable distances to sparse graph classes, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Local 2-separators, Large Induced Subgraphs via Triangulations and CMSO, Efficient First-Order Model-Checking Using Short Labels, Parameterized complexity of finding small degree-constrained subgraphs, Editing graphs to satisfy degree constraints: a parameterized approach, Model-checking hierarchical structures, Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes, Compact labelings for efficient first-order model-checking, Parameterized Counting and Cayley Graph Expanders, A survey of parameterized algorithms and the complexity of edge modification, An optimal construction of Hanf sentences, Unnamed Item, Unnamed Item, Unnamed Item, Computing thejth solution of a first-order query, Unnamed Item, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Dominating set is fixed parameter tractable in claw-free graphs, Practical algorithms for MSO model-checking on tree-decomposable graphs, First-Order Model-Checking in Random Graphs and Complex Networks, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, Reducing CMSO model checking to highly connected graphs, Linearity of grid minors in treewidth with applications through bidimensionality, Graph editing problems with extended regularity constraints, On the fixed-parameter tractability of parameterized model-checking problems, Algorithmic meta-theorems for restrictions of treewidth, Homomorphism preservation on quasi-wide classes, The parameterized complexity of editing graphs for bounded degeneracy, The parameterized complexity of \(k\)-edge induced subgraphs, Finding large degree-anonymous subgraphs is hard, Unnamed Item, On the treewidth of dynamic graphs, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, An Experimental Study of the Treewidth of Real-World Graph Data, On the Parameterised Intractability of Monadic Second-Order Logic, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Uniform Constraint Satisfaction Problems and Database Theory, Parameterized Graph Editing with Chosen Vertex Degrees
