A note on the greedy algorithm for finding independent sets of C_k-free graphs
DOI10.1016/J.IPL.2009.01.009zbMATH Open1209.68645OpenAlexW2075907664MaRDI QIDQ987802FDOQ987802
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
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)
Cites Work
- On maximal paths and circuits of graphs
- Lower bounds on the independence number in terms of the degrees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Vertex packings: Structural properties and algorithms
- A note on the independence number of triangle-free graphs
- A note on Ramsey numbers
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing independent sets in graphs with large girth
- Title not available (Why is that?)
- Coloring Triangle-Free Graphs on Surfaces
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- 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 👍 👎
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)
