A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
type: Item
instance of: scholarly article
title: A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs
zbMATH Open document ID: 1209.68645
author: Ippei Koura
author: Takao Ono
author: Tomio Hirata
published in: Information Processing Letters
publication date: 2010-08-16T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5771245
zbMATH Keywords: approximation algorithms
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: maximum independent set
MaRDI profile type: Publication
full work available at URL: j.ipl.2009.01.009
OpenAlex ID: W2075907664
cites work: A note on Ramsey numbers
cites work: Coloring Triangle-Free Graphs on Surfaces
cites work: On maximal paths and circuits of graphs
cites work: Q5638352
cites work: Q3863917
cites work: Q3872499
cites work: Lower bounds on the independence number in terms of the degrees
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Q4698692
cites work: Vertex packings: Structural properties and algorithms
cites work: Computing independent sets in graphs with large girth
cites work: A note on the independence number of triangle-free graphs
cites work: Q5781249
DOI: 10.1016/J.IPL.2009.01.009
Recommended article: Q4400853
Recommended article: Q3987833
Recommended article: A polynomial-time algorithm for the Independent Set problem in \(\{{P_{10}},C_4,C_6\}\)-free graphs
Recommended article: Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections
Recommended article: Experimental and Efficient Algorithms
Recommended article: An optimal algorithm to find maximum independent set and maximum 2-independent set on cactus graphs
Recommended article: Greedy approximations of independent sets in low degree graphs
Recommended article: Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
Recommended article: A note on the random greedy independent set algorithm
Recommended article: Q3089731
description: scientific article; zbMATH DE number 5771245