Study on the Polynomial-time Algorithms of NP Complete Problems
Shi Hai-lin · Mathematica Applicata · 2001
In this paper, the polynimial time algorithms of the NP complete problems are gained in the algebraical and combinatorial two aspects respectively. Since there were subtours, the linear programming (LP) technics was inefficient in the past, which was used to analysed the travelling salesman problem (TSP). A layer network is developed in the paper, there are another type (uncomplete) subtours. However, the intersect set of the feasible solution sets of the two models don't contain the two subtours basic feasible solution, hence the TSP is solved in polynomial time using LP technics. Meanunile, a polynomial-time lebeling method is gived to search a Hamilton circuit in a graph. Therefore, a new area to analyse the NPC problem is developed.