Monadic NP and graph minors

MaRDI QIDQ4263794zbMATH OpenFDO

Authors Martin Kreidler, Detlef Seese

Publication date 29 March 2000

zbMATH Keywords

Ajtai-Fagin Ehrenfeucht-Fraïssé gamedescriptive complexity theoryfinite model theoryGraph Connectivitygraph minorsindiscerniblesMonadic NPmonadic second-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Connectivity (05C40) Descriptive complexity and finite models (68Q19)

Recommendations

• Monadic NP and built-in trees
• Graph connectivity, monadic NP and built-in relations of moderate degree
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP

Cited in

(6)

• On nowhere dense graphs
• Monadic NP and built-in trees
• Graph connectivity, monadic NP and built-in relations of moderate degree
• Adventures in monotone complexity and TFNP
• Complete problems for monotone NP
• Homomorphism preservation on quasi-wide classes

This page was built for publication: Monadic NP and graph minors

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