CAJ | 학술논문

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G+F是一个弦图而且所添边的边数|F|是最小的,其中最小值|F|称为图G的填充数,表示为f(G).对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图G的填充数f(-G).
종도론관점강,최소전충문제취시재일개도G중첨가변집F,사득도G적모도G+F시일개현도이차소첨변적변수|F|시최소적,기중최소치|F|칭위도G적전충수,표시위f(G).대일반도래설,최소전충문제시NP-곤난적,단시대일사특수도류래설,저개문제시재다항식시간내가해적.본문급출료현도적보도G적전충수f(-G).
The minimum fill-in problem of a graph G, arising from sparse matrix computation and other application fields,is to find a set F of added edges 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. However the problem for the complement (-G) of a chordal graph G is much more complicated. We determine the exact value of fill-in number f(-G) for this class of complementary graphs.