scientific article; zbMATH DE number 1405697

MaRDI QIDQ4938679zbMATH OpenFDO

Authors H. Y. Lau, Hing-Fung Ting

Publication date 5 July 2000

zbMATH Keywords

polynomial-time algorithmindependent setsgreedy heuristicratio bound

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• The greedier the better: an efficient algorithm for approximating maximum independent set
• 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
• Improved approximations of independent sets in bounded-degree graphs

Cited in

(14)

• Greed is good: approximating independent sets in sparse and bounded-degree graphs
• Performance analysis of greedy algorithms for Max-IS and Min-Maxl-Match
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• It is hard to know when greedy is good for finding independent sets
• GreedyMAX-type algorithms for the maximum independent set problem
• Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
• scientific article; zbMATH DE number 792644 (Why is no real title available?)
• scientific article; zbMATH DE number 20942 (Why is no real title available?)
• scientific article; zbMATH DE number 4149905 (Why is no real title available?)
• The potential of greed for independence
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• On sequential heuristic methods for the maximum independent set problem
• The greedier the better: an efficient algorithm for approximating maximum independent set

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 Q4938679)