Ultimate greedy approximation of independent sets in subcubic graphs

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Combinatorial optimization (90C27) Approximation algorithms (68W25) Graph theory (05Cxx)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
It is hard to know when greedy is good for finding independent sets
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
A note on the independence number of triangle-free graphs
Efficient bounds for the stable set, vertex cover and set packing problems
Approximating maximum independent sets by excluding subgraphs
Three short proofs in graph theory
Some simplified NP-complete graph problems
On approximation properties of the independent set problem for low degree graphs
Improved approximations for maximum independent set via approximation chains
Some APX-completeness results for cubic graphs
Clique is hard to approximate within \(n^{1-\epsilon}\)
Greed is good
Linear degree extractors and the inapproximability of max clique and chromatic number
On the Lovász Theta function for Independent Sets in Sparse Graphs
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
Approximation Resistance from Pairwise-Independent Subgroups
On Approximate Solutions for Combinatorial Optimization Problems
Vertex packings: Structural properties and algorithms
On Syntactic versus Computational Views of Approximability
On the independence number of random cubic graphs
Approximating Maximum Clique by Removing Subgraphs
The Monotone Satisfiability Problem with Bounded Variable Appearances
Reducibility among Combinatorial Problems
Improved approximations of independent sets in bounded-degree graphs
Structural Information and Communication Complexity
Fundamentals of Computation Theory
On the complexity of \(k\)-SAT
Greedy approximations of independent sets in low degree graphs

This page was built for publication: Ultimate greedy approximation of independent sets in subcubic graphs