On the Complexity of Approximating the Independent Set Problem.

Piotr Berman Georg Schnitger

Published in: STACS (1989)

Keyphrases

independent set
computational cost
computational complexity
special case
worst case
decision problems
bipartite graph
space complexity
maximum weight