限制的星划分问题  

Constrained star partition problems

作　　者：张同全[1] 李伟东[2] 李建平[2] 

机构地区：[1]云南大学物理科学技术学院非线性中心,云南昆明650091 [2]云南大学数学与统计学院数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2008年第2期109-112,147,共5页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学研究基金资助项目(10561009);云南省教育厅科学研究基金项目(06J011A)

摘　　要：研究了边赋权图上2类具有权重限制L的最小基数星划分问题-最小基数S(L)划分问题和最小基数S∑(L)划分问题的困难性.得到如下结果:①证明了一般图上最小基数S(L)划分问题的NP-完全性;②证明了一般图上最小基数S∑(L)划分问题的NP-完全性,并证明了对于任意小的正数ε,一般图上的最小基数S∑(L)划分问题不存在(3/2-ε)-近似算法,除非P=NP.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.

关 键 词：最小基数 S(L)划分问题 S∑(L)划分问题 NP-完全性 近似算法 

分 类 号：O157.5[理学—数学]