Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
复制标题
识别启发式何时可以逼近最小顶点覆盖已完成以并行访问 NP
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Holger Spakowski
中科院分区：
文献类型：
--
作者：
E. Hemaspaandra;J. Rothe;Holger Spakowski
对于边删除启发式和最大程度的贪婪启发式，我们研究的问题，认识到这些图形的启发式可以近似的最小顶点覆盖的大小在一个常数因子r，其中r是一个固定的有理数。我们的主要结果是，这些问题是完整的一类问题，通过并行访问NP可解。为了实现这些主要的结果，我们还表明，限制的顶点覆盖问题的这些图，其中任何一个这些算法可以找到一个最佳的解决方案仍然是NP难的。
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.