摘要
证明了顶点的权为参数t的线性函数,尺寸为n的可外平面图的最小顶点复盖的耗费函数的折点个数囿界于O(n^(?)),且提出了一个时间复杂性为O(n^(?))的求解算法。
Let G be a n-vertex outerplanar graph whose vertex weights are linear
functions of the parameter t,We prove that the number of breakpoints of the
minimal vertex cover cost function is bounded by O(n(?)).Also,an O(n(?))
algorithm for finding the solution has been designed.
出处
《中山大学学报（自然科学版）》
CAS
CSCD
1991年第2期39-45,共7页
Acta Scientiarum Naturalium Universitatis Sunyatseni
关键词
可外平面图
顶点复盖
NP完全
outerplanar graph
vertex cover
NP-completeness
