The greedier the better: an efficient algorithm for approximating maximum independent set

DOI10.1023/A:1011672624624MaRDI QIDQ5952051zbMATH OpenOpenAlexFDO

Authors H. Y. Lau, Hing-Fung Ting

Publication date 8 January 2002

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1011672624624

zbMATH Keywords

approximationcombinatorial optimizationgreedy algorithmsmaximum independent set

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1405697
• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• Greedy approximations of independent sets in low degree graphs
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem

Cited in

(10)

• Performance analysis of greedy algorithms for Max-IS and Min-Maxl-Match
• It is hard to know when greedy is good for finding independent sets
• GreedyMAX-type algorithms for the maximum independent set problem
• scientific article; zbMATH DE number 4149905 (Why is no real title available?)
• scientific article; zbMATH DE number 20942 (Why is no real title available?)
• scientific article; zbMATH DE number 792644 (Why is no real title available?)
• scientific article; zbMATH DE number 1405697 (Why is no real title available?)
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs

This page was built for publication: The greedier the better: an efficient algorithm for approximating maximum independent set

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