Some APX-completeness results for cubic graphs
Some APX-completeness results for cubic graphs
复制标题
DOI：
10.1016/s0304-3975(98)00158-3
复制
发表时间：
2000-04-28
影响因子：
1.1
通讯作者：
Kann, V
中科院分区：
文献类型：
--
作者：
Alimonti, P;Kann, V
即使对于立方图，也证明了四个基本的图形问题，最小顶点覆盖，最大独立集，最小统治集和最大切割，即使是APX完整的。因此，除非p = np，否则这些问题不接受由三个界定的度量图的输入图上的任何多项式时间近似方案。 （c）2000 Elsevier Science B.V.保留所有权利。
Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three. (C) 2000 Elsevier Science B.V. All rights reserved.