scientific article; zbMATH DE number 6866317
From MaRDI portal
Publication:4638077
DOI10.4230/LIPIcs.ITCS.2017.27zbMath1402.68077arXiv1612.08192MaRDI QIDQ4638077
Publication date: 3 May 2018
Full work available at URL: https://arxiv.org/abs/1612.08192
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Model theory of finite structures (03C13) Interpolation, preservation, definability (03C40) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)
Related Items (3)
A polynomial excluded-minor approximation of treedepth ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ The descriptive complexity of subgraph isomorphism without numerics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
- The core of a graph
- Finite model theory and its applications.
- Elements of finite model theory.
- Properties preserved under homomorphism
- Homomorphism preservation on quasi-wide classes
- First-order definability on finite structures
- Improved depth lower bounds for small distance connectivity
- The gap between monotone and non-monotone circuit complexity is exponential
- On digraph coloring problems and treewidth duality
- Tree-depth, subgraph coloring and homomorphism bounds
- On first-order definable colorings
- A counterexample to a conjecture of Scott and Suppes
- Preservation under Extensions on Well-Behaved Finite Structures
- On preservation under homomorphisms and unions of conjunctive queries
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Homomorphism preservation theorems
- Undirected connectivity in log-space
- Monotone versus positive
- Approximation and Small-Depth Frege Proofs
- On Preservation Theorems for Two-Variable Logic
- Color-coding
- Faster decision of first-order graph properties
- LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM
- Polynomial bounds for the grid-minor theorem
- Formulas vs. circuits for small distance connectivity
- Near-optimal small-depth lower bounds for small distance connectivity
This page was built for publication:
