前言最近开始学习近似算法,在Coursera上找到了一门课:地址。在此按照课程每周的内容,各写一篇blog来总结、分享。 Week 1: Vertex Cover Problem Definition:最小点覆盖,即给出一个无向图,求一个最小的点集$S$,使得每条边都至少有一个顶点在这个点集里。 已有知识: 树的最小点覆盖很容易用$O(|V|)$的时间求出: 动态规划:$dp[v][0/1]$ 表示,最少需要多少个点来覆盖以$v$为根的子树,第二维$0/1$表示$v$和它父亲节点之间的边是否已经被覆盖, 转移考虑点$v$选还是不选,从子树的结果转移即可。 贪心:从叶子节点考虑,每个叶子节点和它 ...