The descriptive complexity of subgraph isomorphism without numerics

DOI10.1007/S00224-018-9864-3MaRDI QIDQ6830314zbMATH OpenFDO

Authors Oleg Verbitsky, M. E. Zhukovskii

Publication date 4 July 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-018-9864-3

zbMATH Keywords

descriptive complexityencoding-independent computationfirst-order logicquantifier depthsubgraph isomorphism problem

Mathematics Subject Classification ID

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

Cited in

(2)

• First order complexity of finite random structures
• On the validity of 0-1 law for shallow first order properties of very sparse random graphs

This page was built for publication: The descriptive complexity of subgraph isomorphism without numerics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6830314)