| 带参数可外平面图的一个算法 |
| |
| 引用本文： | 朱秉寰.带参数可外平面图的一个算法[J].中山大学学报(自然科学版),1991,30(2):39-45. |
| |
| 作者姓名： | 朱秉寰 |
| |
| 作者单位： | 中山大学计算机科学系 |
| |
| 摘 要： | 证明了顶点的权为参数t的线性函数,尺寸为n的可外平面图的最小顶点复盖的耗费函数的折点个数囿界于O(n~(?)),且提出了一个时间复杂性为O(n~(?))的求解算法。
|
| 关 键 词： | 可外平面图 顶点复盖 NP完全 |
An Algorithm for Parametric Outerplanar Graphs |
| |
| Zhu Binghuan.An Algorithm for Parametric Outerplanar Graphs[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,1991,30(2):39-45. |
| |
| Authors: | Zhu Binghuan |
| |
| Institution: | Zhu Binghuan Department of Computer Science |
| |
| Abstract: | 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. |
| |
| Keywords: | outerplanar graph vertex cover NP-completeness |
| 本文献已被 CNKI 维普 等数据库收录！ |
