| 关于英文版 « 9.15. 3-SAT 到团的归约 :: 目录 :: 9.17. 3-SAT 到哈密顿回路的归约 »

9.16. 独立集到顶点覆盖的归约¶

9.16.1. 独立集到顶点覆盖¶

下面的幻灯片表明， INDEPENDENT SET 的一个输入实例可以在多项式时间内归约为 VERTEX COVER 的一个等价输入实例。

Proficient

Saving...

Error Saving

Server Error
Resubmit

这个归约有助于为顶点覆盖（Vertex Cover）问题提供 NP 完全性证明。

隐私 | | 许可协议 « 9.15. 3-SAT 到团的归约 :: 目录 :: 9.17. 3-SAT 到哈密顿回路的归约 »