摘要
图的树宽问题是著名的 NP-困难问题 .其分解原则在确定树宽的一般算法和特殊算法中有重要应用 .本文给出这方面的若干定理 .
The treewidth problem of graphs is known to be NP hard. The decomposition principle is useful in the general and special algorithms for determining treewidth. This paper presents some theorems in this aspect.
出处
《数学研究》
CSCD
2000年第2期113-120,共8页
Journal of Mathematical Study
基金
Projectsupported by the Natural Science Foundation of China (1 9771 0 75)
关键词
弦图
树宽
分解定理
图
算法
chordal graph, treewidth, decomposition
