A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs

DOI10.1016/j.ipl.2009.01.009zbMath1209.68645MaRDI QIDQ987802

Tomio Hirata, Ippei Koura, Takao Ono

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.009

zbMATH Keywords

analysis of algorithms; approximation algorithms; maximum independent set

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• Computing independent sets in graphs with large girth
• Lower bounds on the independence number in terms of the degrees
• On maximal paths and circuits of graphs
• Vertex packings: Structural properties and algorithms
• Coloring Triangle-Free Graphs on Surfaces