原书出处
Introduction to Algorithms, Fourth Edition
35 第35章 近似算法
ializes C to the empty set. Line 2 sets E′ to be a copy of the edge set G.E of the graph.
The while loop of lines 3–6 repeatedly picks an edge (u, v) from E′, adds its endpoints u and v into C, and deletes all edges in E′ that u or v covers. Finally, line 7 returns the vertex cover C. The running time of this algorithm is O(V + E), using adjacency lists to represent E′. APPROX-VERTEX-COVER (G) 1 C = Ø 2 E′ = G.E 3
while E′ ≠ Ø 4 let (u, v) be an arbitrary edge of E′ 5 C = C ∪ {u, v} 6 remove from E′ ed
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter035.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea