序列平行图的最小填充(英文)  

On Minimum Fill-in for Series-parallel Graphs

作　　者：张振坤[1] 王峥[2] 

机构地区：[1]黄淮学院数学系,河南驻马店463000 [2]郑州铁路职业技术学院公共教学部,河南郑州450052

出　　处：《应用数学》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)

摘　　要：起源于稀疏矩阵计算和其它应用领域的一个图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.

关 键 词：弦图 填充数 序列平行图 分解树 

分 类 号：O157.5[理学—数学]