|
|||||
|
|
| 最小权点覆盖问题的一个近似算法 | |
| 作者单位： | ;1.兰州交通大学数理学院 |
| 摘 要： | 在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性. |
| 关 键 词： | 最小点覆盖问题 Dijkstra算法 近似算法 时间复杂性 |
An Approximation Algorithm for Minimum Weighted Vertex Cover Problem |
|
| Abstract: | |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ | |
