k-树的补图的最小填充和树宽(英文)

On Minimum Fill-in and Treewidth of the Complements of k-Trees

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．

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 k-tree G, denoted by -↑G, is called a k-cotree. In this paper, we determine the minimum fill-in number f（-↑G） and the treewidth TW（-↑G） of a k-cotree -↑G.