scientific article; zbMATH DE number 792644

zbMATH Open0832.90094MaRDI QIDQ4845153FDOQ4845153

Authors: Vangelis Th. Paschos 

Publication date: 4 September 1995

Title of this publication is not available (Why is that?)

Recommendations

• Improved approximations for maximum independent set via approximation chains
• A note on the approximation of a minimum-weight maximal independent set
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• An improvement on the maximum number of \(k\)-dominating independent sets
• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• Publication:4938679
• scientific article; zbMATH DE number 1222591
• Improved approximations of independent sets in bounded-degree graphs
• scientific article; zbMATH DE number 1003268
• The greedier the better: an efficient algorithm for approximating maximum independent set

zbMATH Keywords

approximationmaximum independent set problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (1)

• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4845153)