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

DOI10.1016/J.IPL.2009.01.009MaRDI QIDQ987802zbMATH OpenOpenAlexFDO

Authors Ippei Koura, Takao Ono, Tomio Hirata

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

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

Recommendations

• scientific article; zbMATH DE number 1182770
• scientific article; zbMATH DE number 31760
• A polynomial-time algorithm for the Independent Set problem in \(\{{P_{10}},C_4,C_6\}\)-free graphs
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Experimental and Efficient Algorithms
• An optimal algorithm to find maximum independent set and maximum 2-independent set on cactus graphs
• Greedy approximations of independent sets in low degree graphs
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• A note on the random greedy independent set algorithm
• Algorithmic results of independent \(k\)-domination on weighted graphs

Cites work

• scientific article; zbMATH DE number 3664996 (Why is no real title available?)
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 753971 (Why is no real title available?)
• scientific article; zbMATH DE number 3365308 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• Coloring Triangle-Free Graphs on Surfaces
• Computing independent sets in graphs with large girth
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Lower bounds on the independence number in terms of the degrees
• On maximal paths and circuits of graphs
• Vertex packings: Structural properties and algorithms

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

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