AN APPROXIMATION ALGORITHM FOR THE MAXIMUM INDEPENDENT SET PROBLEM ON PLANAR GRAPHS

作     者：CHIBA, N NISHIZEKI, T SAITO, N 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1982年第11卷第4期

页      面：663-675页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：approximation algorithm maximum independent set problem bounded worst case ratio time-complexity planar graph vertex-identification 

摘      要：In this paper we consider the maximum independent set problem in which one would like to find a maximum set of independent (i.e., pairwise nonadjacent) vertices in a given graph. The problem is NP-complete, and still remains so even if we restrict ourselves to the class of planar graphs. It has been conjectured that there exist no polynomial-time exact algorithms for any NP-complete problems. We present a polynomial-time approximation algorithm for the maximum independent set problem on planar graphs. For a given planar graph having any number n of vertices, our algorithm finds, in O(nlogn) role=presentationO(nlognspan clas