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

DOI10.1023/A:1011672624624zbMATH Open1135.90425OpenAlexW3163150419MaRDI QIDQ5952051FDOQ5952051

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

Recommendations

• Publication:4938679
• 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

zbMATH Keywords

combinatorial optimizationapproximationgreedy algorithmsmaximum independent set

Mathematics Subject Classification ID

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

Cited In (9)

• Title not available (Why is that?)
• It is hard to know when greedy is good for finding independent sets
• Performance analysis of greedy algorithms for Max-IS and Min-Maxl-Match
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
• GreedyMAX-type algorithms for the maximum independent set problem
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

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)