CAJ | 학술논문

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G+F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.
기원우희소구진계산화기타응용영역적도G적최소전충문제시재도G중심구일개내함변수최소적변집F사득G+F시현도.저리최소치|F|칭위도G적전충수,표시위f(G).작위NP-곤난문제,해문제적강유성질이피연구,기중포괄타적가분해성.기본적가분해정리시:여과도G적일개점할집S시일개단,칙G경유S시가분해적.작위추엄,여과S시일개"근사"단(즉지유겁소수변주실적단),칙G경유S시가분해적.본문수선급출기본분해정리적령외일개추엄:여과S시G적일개겁소점할집차G-S함유지소|S|개분지,칙G경유S시가분해적;기차,급출료저개신추엄정리적일사응용.
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.