Constrained star partition problems
Tongquan Zhang · Yunnan Daxue xuebao. Shehui kexue ban · 2008
Two problems of star partition with some restrictions on edge weighted graphs were considered here,i.e.minamal cardinality S(L) partition problemand Minamal cardinality S ∑(L) partition problem,the following results were obtained,① Minamal cardinality S(L) partition problem's NP-Completeness was proved on general graphs;② Minamal cardinality S ∑(L) partition problem's NP-Completeness was proved on general graphs,too,and for any small numbere,there is no(3/2-e)-approximate algorithm for Minamal cardinality S ∑(L) partition problem on general graphs,unless P=NP.