|
|||||
|
|
| k-树的补图的最小填充和树宽 | |
| 引用本文： | 张振坤,王秀梅,林诒勋. k-树的补图的最小填充和树宽[J]. 运筹学学报, 2006, 10(2): 59-68 |
| 作者姓名： | 张振坤 王秀梅 林诒勋 |
| 作者单位： | 郑州大学数学系,郑州,450052 |
| 基金项目： | Acknowledgements： The authors would like to thank Prof. Yuan Jinjiang for his helpful suggestions. |
| 摘 要： | 一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)． |
| 关 键 词： | 运筹学 组合优化 填充 树宽 k-树 k-补树 团树 |
| 收稿时间： | 2005-04-11 |
| 修稿时间： | 2005-04-11 |
On Minimum Fill-in and Treewidth of the Complements of k-Trees |
|
| Zhang Zhenkun,Wang Xiumei,Lin Yixun. On Minimum Fill-in and Treewidth of the Complements of k-Trees[J]. OR Transactions, 2006, 10(2): 59-68 | |
| Authors: | Zhang Zhenkun Wang Xiumei Lin Yixun |
| Affiliation: | Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China |
| Abstract: | The minimum fill-in problem of a graph is to find a chordal supergraph with the smallest possible number of edges. The treewidth problem of a graph is to find a chordal supergraph with the smallest possible cliquesize. These two problems have important applications to sparse matrix computation and graph algorithm design, respectively. The complement of a fc-tree G, denoted by G, is called a fc-cotree. In this paper, we determine the minimum fill-in number f(G) and the treewidth TW(G) of a fc-cotree G. |
| Keywords: | Operation research combinatorial optimization fill-in treewidth k-tree k-cotree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |