Year: 2014
Volume: 6
Issue: 2

Transforming 3SAT to Steiner problem in planar graph which is NP-complete

Author:
G. Nirmala, C. Sujatha
Total Page Count: 8
Page Number: 365 to 372

*Head & Associate Professor, PG & Research, Dept. of Mathematics, K.N. Govt. Arts College for women (Autonomous), Thanjavur-613007. (Tamilnadu)

**Research Scholar, Dept. of Mathematics, K.N. Govt. Arts College for women (Autonomous), Thanjavur-613007

Online published on 10 February, 2015.

Abstract

Complexity theory has many facts. In this work, we propose an NP-completeness result for the Steiner problem in planar graphs.

Keywords

Planar graph, NP-complete, Steiner problem in planar graph, 3-Satisfiability