On strongly planar 3SAT |
| |
| Authors: | Lidong Wu |
| |
| Affiliation: | 1.Department of Computer Science,University of Texas at Tyler,Tyler,USA |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
