Satisfiability of co-nested formulas

DOI10.1007/BF01209713zbMath0790.68050MaRDI QIDQ1323332

Jan Kratochvíl, Mirko Křivánek

Publication date: 2 June 1994

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

decidabilitysatisfiabilityco-nested formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Decidability of theories and sets of sentences (03B25)

Related Items (5)

Max Horn SAT and the minimum cut problem in directed hypergraphs ⋮ Optimization and probabilistic satisfiability on nested and co-nested formulas ⋮ Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable ⋮ New tractable classes for default reasoning from conditional knowledge bases ⋮ Planar 3-SAT with a clause/variable cycle

Cites Work

• Nested satisfiability
• The complexity of induced minors and related problems
• Noncrossing Subgraphs in Topological Layouts
• Planar Formulae and Their Uses
• Efficient Planarity Testing
• The Planar Hamiltonian Circuit Problem is NP-Complete

This page was built for publication: Satisfiability of co-nested formulas