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

DOI10.1016/j.ipl.2009.01.009zbMath1209.68645OpenAlexW2075907664MaRDI 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 algorithmsapproximation algorithmsmaximum independent set

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

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

This page was built for publication: A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs