← 返回起始笔记位置

知识卡片

普通读书笔记卡 · 3717.a

顶点覆盖归约的规模界

理解等级:高级

顶点覆盖到哈密顿环的构造为每条原边配置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.