一类NP-完全问题在阈图上的解

SOLUTION OF A CLASS OF NP-C PROBLEMS IN THRESHOLD GRAPH

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。

This paper presents a polynomial algorithm to determine whether a threshold graph is a Hamiltonian graph. It is also shown that STEINER tree problem in threshold graph is NP-complete and a polynomial approximate algorithm for it is proposed.