星划分数的计算复杂性及其与支配数的联系

摘要：

分别证明了"确定任意无向简单图星划分数与支配数是否相等"、"求二分平面图的星划分数"与"任意无向简单图的星划分数是否等于3"等三个问题是NP-完全的.

关键词：星划分、星划分数、支配集、支配数、计算复杂性、NP-完全

所属期刊栏目：19

分类号：O157.5(代数、数论、组合理论)

资助基金：广东省科技攻关项目C31801;广东省自然科学基金010060

在线出版日期：2004-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：25-29