知识卡片
归约构件强制局部性质
归约构件是嵌入新实例的局部组件,通过连接方式限制解的形态。
顶点覆盖到哈密顿环的边构件约束环如何穿过12个顶点;子集和中的松弛数也可视为使子句位补到目标值的简单构件。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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