Top

Journal of Combinatorial Optimization

Published in:

01-07-2016

On strongly planar 3SAT

Author: Lidong Wu

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The strongly planar 3SAT problem is NP-complete. This fact is proved in a book (Du et al. in Introduction to computational complexity theory, 2002). We show that the strongly planar 1-in-3SAT and strongly planar not-all-equal 3SAT problems are also NP-complete. They are very useful in study of combinatorial optimization problems in a plane.

previous article Distributed wireless link scheduling in the SINR model

next article Signed mixed Roman domination numbers in graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Du D-Z, Ko Ker-I, Wang Jie (2002) Introduction to computational complexity theory. High Education Publisher, Beijing (in Chinese)

Dyer MD, Frieze AM (1986) Planar 3DM is NP-complete. J Algorithm 7:174–184MathSciNetCrossRefMATH

Lichtenstein D (1982) Planar formulae and their uses. SIAM J Comput 11:329–343MathSciNetCrossRefMATH

Title: On strongly planar 3SAT
Author: Lidong Wu
Publication date: 01-07-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9878-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Special Issue for FAW 2014

Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Constrained pairwise and center-star sequences alignment problems

Upper bounds for the total rainbow connection of graphs

Signed mixed Roman domination numbers in graphs

Dynamic matchings in left vertex weighted convex bipartite graphs

Premium Partner