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

广东工业大学学报 ›› 2002, Vol. 19 ›› Issue (3): 25-29.

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

广东工业大学自动化学院；广东工业大学自动化学院广东广州510090；广东广州510090；

出版日期:2002-09-04 发布日期:2002-09-04
基金资助:
广东省科技攻关资助项目(C31801);广东省自然科学基金资助项目(010060).

Complexities of Star Partition Number and Its Connections with Domination Number

(Faculty of Automation,GDUT,Guangzhou 510090,China)

Online:2002-09-04 Published:2002-09-04

摘要/Abstract

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

蔡延光；张新政； . 星划分数的计算复杂性及其与支配数的联系[J]. 广东工业大学学报, 2002, 19(3): 25-29.

CAI Yanguang,ZHANG Xinzheng. Complexities of Star Partition Number and Its Connections with Domination Number[J]. Journal of Guangdong University of Technology, 2002, 19(3): 25-29.

[1] 周永生,蔡延光. 树的有效支配集[J]. 甘肃工业大学学报. 1991(01)

[2] 刘松,蔡延光. 树的m—路中心[J]. 重庆大学学报(自然科学版). 1991(04)

[3] 蔡延光,钱积新,孙优贤. 受限p-中心的并行迭代算法[J]. 系统工程理论与实践. 2000(07)

[4] 蔡延光. 图的增广支配数[J]. 湖北汽车工业学院学报. 1999(01)

[5] 蔡延光,石庆忠. 树的受限P—中心[J]. 湖北汽车工业学院学报. 1992(02)

[1] Stockmeyer L J.Planar 3-colorability is NP-complete. SIGACT News . 1973

[2] Acharya B D,Walikar H B.On graphs having unique minimum dominating sets. Graph Theory Newsletter . 1979

[3] Yannkakis M,Gavril F.Edge dominating sets in graphsSIAM J. Journal of Applied Mathematics . 1980

[4] Bondy J A,Murty U S R.Graph Theory with Applications. . 1976

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed