应用数学2008，Vol.21Issue(2)：354-361,8.
最小填充问题的可分解性
The Decomposability of Minimum Fill-in Problems for Graphs
摘要
Abstract
The fill-in minimization problem comes from the elimination process of sparse matrix computation.In a graph-theoretic version for a graph G,it is to find a set F of added edges such that the graph G+F is chordal and |F| is minimized.Here the minimum value |F| is called the finll-in number of G,denoted as f(G).This problem is known to be NP-hard.Some techniques of dimension reduction,including the decomposability of the problem,were studied in the literatures.The basic decomposition result is that if a vertex cut S of G is a clique,then G is decomposable by S.A direction of generalization is that when the cut is 'nearly' a clique (a clique with a few edges missing),G is decomposable by S.This paper presents another direction of generalization that if S is a minimal vertex cut of G and G-S has at least |S| components,then G is decomposable by S.Some applications of this theorem are also discussed.关键词
图标号/填充数/弦图/分解定理Key words
Graph labeling/Fill-in number/Chordal graph/Decomposition theorem分类
数理科学引用本文复制引用
张振坤,王秀梅,林诒勋..最小填充问题的可分解性[J].应用数学,2008,21(2):354-361,8.基金项目
Supported by the National Natural Science Foundation of China (10671183) （10671183）
