DocumentCode :
2516557
Title :
A note on the P-time algorithms for solving the maximum independent set problem
Author :
Esfahani, Navid Nasr ; Mazrooei, Parisa ; Mahdaviani, Kaveh ; Omoomi, Behnaz
Author_Institution :
Dept. of Electr. & Comput. Eng., Isfahan Univ. of Technol., Isfahan, Iran
fYear :
2009
fDate :
27-28 Oct. 2009
Firstpage :
65
Lastpage :
70
Abstract :
In this article, the problem of finding maximum (weight) independent set (M(W)IS) is investigated. It is known that this problem belongs to the class of NP-hard problems. Although, there are polynomial time (P-time) algorithms to solve the M(W)IS problem for some special classes of graphs. Here, we propose a general scheme which extends all of classes that the M(W)IS problem is solvable for them in P-time. This general scheme, based on any P-time algorithm for a class of graphs C, generates a new P-time algorithm to solve the M(W)IS problem for graphs in an extension of the class C. Moreover, this new algorithm is robust.
Keywords :
computational complexity; graph theory; set theory; NP-hard problem; P-time algorithm; graph theory; maximum independent set problem; polynomial time algorithm; Data mining; Graph theory; NP-hard problem; Polynomials; Robustness; Virtual reality; Exact optimization algorithm; Maximum independent set problem; Maximum weight independent set problem;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Mining and Optimization, 2009. DMO '09. 2nd Conference on
Conference_Location :
Kajand
Print_ISBN :
978-1-4244-4944-6
Type :
conf
DOI :
10.1109/DMO.2009.5341909
Filename :
5341909
Link To Document :
بازگشت