| 弦图上团划分数问题的复杂性 |
| |
| 引用本文： | 马绍汉,吴举林.弦图上团划分数问题的复杂性[J].山东大学学报(理学版),1989(2). |
| |
| 作者姓名： | 马绍汉 吴举林 |
| |
| 作者单位： | 山东大学计算机科学系，青岛大学数学系 |
| |
| 摘 要： | 本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。
|
| 关 键 词： | 弦图 团覆盖数 团划分数 NP——困难性 |
THE COMPLEXITY OF THE CLIGUE PARTITION NUMBER IN CHORDAL GRAPHS |
| |
| Ma Shaohan Wu Julin.THE COMPLEXITY OF THE CLIGUE PARTITION NUMBER IN CHORDAL GRAPHS[J].Journal of Shandong University,1989(2). |
| |
| Authors: | Ma Shaohan Wu Julin |
| |
| Abstract: | 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. |
| |
| Keywords: | chordal graph cligue covering number cligue partition number NP-hardness |
| 本文献已被 CNKI 等数据库收录！ |
