APPROXIMATING THE MINIMUM MAXIMAL INDEPENDENCE NUMBER

被引：78

作者：

HALLDORSSON, MM

机构：

[1] School of Information Science, Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 46卷 / 04期

关键词：

COMBINATORIAL PROBLEMS; APPROXIMATION ALGORITHMS;

D O I：

10.1016/0020-0190(93)90022-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the problem of approximating the size of a minimum non-extendible independent set of a graph, also known as the minimum dominating independence number. We strengthen a result of Irving to show that there is no constant epsilon > 0 for which this problem can be approximated within a factor of n1-epsilon in polynomial time, unless P = NP. This is the strongest lower bound we are aware of for polynomial-time approximation of an unweighted NP-complete graph problem.

引用

页码：169 / 172

页数：4