摘要
起源于稀疏矩阵计算和其它应用领域的一个图G的最小填充问题就是在G中寻找一个边数|F|最小的添加边集F,使得G+F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).对一般图来说,这个问题是NP-困难问题.一些特殊图类的最小填充问题已被研究.本文给出了序列平行图G的最小填充数的具体值.
The minimum fill-in problem of a graph G,stemming from sparse matrix computations and other application fields,is to find a set F of edges added such that G+F is chordal and |F| is minimized.Here the minimum value |F| is called the fill-in number of G,denoted by f(G).The problem is known to be NP-hard for general graphs.Some classes of special graphs have been investigated in the literatures.In this paper we determine the exact value of fill-in number f(G)for the series-parallel graphs.
出处
《应用数学》
CSCD
北大核心
2010年第1期130-137,共8页
Mathematica Applicata
基金
Supported by the Natural Science Foundation of Henan Province(082300460190)
Sponsored by Program for Science and Technology Innovation Talents in Universities of Henan Province(2010HASTIT043)
关键词
弦图
填充数
序列平行图
分解树
Chordal graph
Fill-in number
Series-parallel graph
Decomposition tree
