TOPICS
Search

Maximum Independent Set Problem

This problem is NP-complete (Garey and Johnson 1983).

See also

Claw-Free Graph, Independent Set, Maximum Independent Edge Set, Maximum Independent Vertex Set

References

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Referenced on Wolfram|Alpha

Maximum Independent Set Problem

Cite this as:

Weisstein, Eric W. "Maximum Independent Set Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MaximumIndependentSetProblem.html