Study On Maximum Clique And Maximum Weighted Independent Set Problem Based On Q0-1 Programming

The pr oblems of maximum clique and maximum independent set in arbitrary graph are well-known classical NP-complete. Owing to their profound academic and applied background, recently, exploring an exact algorithm or heuristics as fine as possible of these problems is hotspot for so many mathematicians.In this paper, we firstly present mathematical meanings and relationship between maximum clique and maximum independent set. The expatiation of investigation actuality about these problems emphasized in the ideas and general flows of various exact algorithms and heuristics.Secondly, we present the general form and background of Q0-1 programmingminf(X)= C^TX + 1/2X^T QX,X∈{0,1}ⁿ(C is a rational vector of order n, Q = (q_ij )_n×n is a rational matrix of order n×n),branch and bound algorithm for this model is discussed in detail in this chapter. Model and algorithm in our paper root in the model and algorithm we discuss above.Based on above model, author bring forward a more compact Q0-1 programming. It has more close corresponding connection with the basal invaribals of given graph. Following in this model, we firstly present the...