Anzeige
Erschienen in:
01.10.2016
On strongly planar not-all-equal 3SAT
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2016
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper we show that there is a polynomial time algorithm for the strongly planar not-all-equal 3SAT problem. Also, we prove that a restricted version of planar not-all-equal 3SAT is \( \mathbf {NP} \)-complete and in consequence of this result, we show that for a given planar bipartite graph \(G\), deciding whether there is a vertex-labeling by gap from \(\{1,2\}\) such that the induced proper coloring is a proper vertex 2-coloring is \( \mathbf {NP} \)-complete.