知识卡片

普通读书笔记卡 · 3714.b.8.c

归约构件强制局部性质

理解等级:初级

归约构件是嵌入新实例的局部组件,通过连接方式限制解的形态。

顶点覆盖到哈密顿环的边构件约束环如何穿过12个顶点;子集和中的松弛数也可视为使子句位补到目标值的简单构件。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第34章 NP完全性 · 查看原书依据

      Design gadgets The reduction from the vertex-cover problem to the hamiltonian-cycle problem uses the gadget shown in Figure 34.16. This gadget is a subgraph that is connected to other parts of the constructed graph in order to restrict the ways that a cycle can visit each vertex in the gadget once. More generally, a gadget is a component that enforces

    参考来源

    - 位置:《算法导论(第4版)》第34章《NP完全性》(OEBPS/chapter034.xhtml,文本字符[120000,125000))。 - 结论依据:原文归约策略、习题定义与脚注限定;图34.20–34.21已核对,习题未给出的证明不作既成结论。 - 原始内容:Design gadgets The reduction from the vertex-cover problem to the hamiltonian-cycle problem uses the gadget shown in Figure 34.16 . This gadget is a subgraph that is connected to other parts of the constructed graph in order to restrict the ways that a cycle can visit each vertex in the gadget once. More generally, a gadget is a component that enforces