知识卡片
顶点覆盖归约的规模界
顶点覆盖到哈密顿环的构造为每条原边配置12个顶点,另加k个选择顶点;内部边、构件间边和选择边也都只有多项式数量。
证明归约时须同时给出规模界与双向正确性,不能只展示图形。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第34章 NP完全性 · 查看原书依据
Next we show that the size of G′ is polynomial in the size of G, and hence it takes time polynomial in the size of G to construct G′. The vertices of G′ are those in the gadgets, plus the selector vertices. With 12 vertices per gadget, plus k ≤ |V | selector vertices, G′ contains a total of |V′| = 12 |E| + k ≤ 12 |E| + |V| vertices.
参考来源
- 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[100000,105000))。
- 结论依据:第34章原文中的定义、规模界及双向归约证明;涉及图34.17–34.19时已核对图像。
- 原始内容:Next we show that the size of G ′ is polynomial in the size of G , and hence it takes time polynomial in the size of G to construct G ′. The vertices of G ′ are those in the gadgets, plus the selector vertices. With 12 vertices per gadget, plus k ≤ | V | selector vertices, G ′ contains a total of | V′ | = 12 | E | + k ≤ 12 | E | + | V | vertices.