scientific article

zbMath1432.03049arXiv1704.02237MaRDI QIDQ3121527

Oleg Verbitsky, M. E. Zhukovskii

Publication date: 18 March 2019

Full work available at URL: https://arxiv.org/abs/1704.02237

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

descriptive and computational complexityfinite-variable first-order logicinduced subgraph isomorphism problemquantifier depth and variable width

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items (2)

First-order definitions of subgraph isomorphism through the adjacency and order relations ⋮ The descriptive complexity of subgraph isomorphism without numerics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• On the complexity of fixed parameter clique and dominating set
• Elements of finite model theory.
• Strong computational lower bounds via parameterized complexity
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• The connectivity of strongly regular graphs
• Paw-free graphs
• Complement reducible graphs
• Succinct definitions in the first order theory of graphs
• Decomposable graphs and definitions with no quantifier alternation
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Logical complexity of graphs: a survey
• Powers of tensors and fast matrix multiplication
• A Linear Recognition Algorithm for Cographs
• Finding a Minimum Circuit in a Graph
• Color-coding
• How complex are random graphs in first order logic?
• Finding Four-Node Subgraphs in Triangle Time
• Detecting and Counting Small Pattern Graphs
• On the $AC^0$ Complexity of Subgraph Isomorphism
• The descriptive complexity of subgraph isomorphism without numerics
• The strange logic of random graphs

This page was built for publication: