Abstract:
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 numberε,there is no(3/2-ε)-approximate algorithm for Minamal cardinality S ∑(L)partition problem on general graphs,unless P=NP.