scientific article; zbMATH DE number 4094812

MaRDI QIDQ3821582zbMATH OpenFDO

Authors Bernard M. E. Moret

Publication date 1988

zbMATH Keywords

NAE3SATNP-completenessplanar graphsSimple MaxCut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 152108
• The Complexity of Planar Counting Problems
• On strongly planar 3SAT
• On strongly planar not-all-equal 3SAT
• Planar 3-SAT with a clause/variable cycle

Cited in

(23)

• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Positive planar satisfiability problems under 3-connectivity constraints
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• On planar valued CSPs
• Colorful edge decomposition of graphs: some polynomial cases
• Simultaneous orthogonal planarity
• On strongly planar not-all-equal 3SAT
• On strongly planar 3SAT
• On Planar Boolean CSP
• Planar 3DM is NP-complete
• Algorithmic complexity of proper labeling problems
• scientific article; zbMATH DE number 152108 (Why is no real title available?)
• Computing k-modal embeddings of planar digraphs
• Planar 3-SAT with a clause/variable cycle
• Planar 3-SAT with a clause/variable cycle
• Polychromatic colorings of plane graphs
• \(st\)-orientations with few transitive edges
• Relating planar graph drawings to planar satisfiability problems
• $st$-Orientations with Few Transitive Edges
• Cutting Barnette graphs perfectly is hard
• On the restrained domination stability in graphs
• Some NP-complete edge packing and partitioning problems in planar graphs
• On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

This page was built for publication:

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