弦图上团划分数问题的复杂性  

THE COMPLEXITY OF THE CLIGUE PARTITION NUMBER IN CHORDAL GRAPHS

作　　者：马绍汉[1] 吴举林[2] 

机构地区：[1]山东大学计算机科学系 [2]青岛大学数学系

出　　处：《山东大学学报（自然科学版）》1989年第2期14-19,共6页Journal of Shandong University(Natural Science Edition)

摘　　要：本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。The main results of this paper are that (1) the cligue partition problems over K_4-free graphs or chordal graphs are NP-hard; (2) a linear time algorithm for the cligue partition problem over K_4-free chordal graphs and a linear time algoeithm for the cligue covering over chordal graphs are presented.

关 键 词：弦图 图覆盖数 团划分数 NP-困难 

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