原书出处
Introduction to Algorithms, Fourth Edition
35 第35章 近似算法
—in particular, an optimal cover C*—must include at least one endpoint of each edge in A.
No two edges in A share an endpoint, since once an edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E′ in line 6. Thus, no two edges in A are covered by the same vertex from C*, meaning that for every vertex in C*, there is at most one edge in A, giving the lower bound on the size of an optimal
vertex cover. Each execution of line 4 picks an edge for which neither of its endpoints i
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter035.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea