毛虫树的扩充侧廓

The Extended Profile of the Caterpillars

起源于20世纪50年代的稀疏矩阵的存贮和消去技术的图的扩充侧廓问题就是在一个图G中寻求一个内含边数最小的边集F,使得超图G+F是单位区间图.G+F的边数|G+F|称为图G的扩充侧廓,表示为(?)(G);最小值|F|称为图G的单位区间完全数,表示为pic(G).文章得到了毛虫树的扩充侧廓的多项式时间算法和直径为4的特殊毛虫树的扩充侧廓具体表达式.

The extended profile problem of a graph of the storage and elimination technique in 1950＇s is to find a set F with least edges in graph G, and make the graph G＋F is a proper interval graph. The edge number ｜G＋F｜ of G＋F is called the extended profile, denoted as ~↑P（G）, and the minimum value ｜F｜ is called the proper interval complete number, denoted as pic（G）. This paper provides a polynomial time algorithm to compute the extended profile of the caterpillars, and as an instance, the extended profile ~↑P（G） for the caterpillars with diameter four is given.