Approximation of independent sets in graphs
Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Ramsey theory (05D10) Graph theory (including graph drawing) in computer science (68R10)
This paper is an introduction to the performance ratios of a selection of independent set approximation algorithms. From the author's introduction: The primary criteria for selection was (sic) simplicity of the algorithm and the proof. We state some observations that have not formally appeared before, give some recent results, and present simpler proofs of other results. \dots{} We present a number of particular results illustrating particular algorithmic strategies: subgraph removal, semi-definite programming, partitioning, greedy algorithms, and local search. We give a listing of known performance results, and finish with a discussion of open issues. For the entire collection see [Zbl 0892.00051].
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Computing independent sets in graphs with large girth
- Approximating maximum independent sets by excluding subgraphs
- On approximation properties of the independent set problem for low degree graphs
- Approximating weighted neighborhood independent sets
- Conversion of coloring algorithms into maximum weight independent set algorithms
- On the approximability of clique and related maximization problems
- Efficient independent set approximation in unit disk graphs
- Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
- On the complexity of the independent set problem in triangle graphs
- The complexity of dissociation set problems in graphs
- Complexity results for rainbow matchings
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Approximation algorithms for independent sets in map graphs
- GreedyMAX-type algorithms for the maximum independent set problem
- Combinatorial auctions with conflict-based externalities
- On Lagrangian Relaxation and Subset Selection Problems
- Geometric rounding: A dependent randomized rounding scheme
- Approximation algorithms for maximum independent set of pseudo-disks
- scientific article; zbMATH DE number 910871 (Why is no real title available?)
- On constant time approximation of parameters of bounded degree graphs
- Fast heuristics and approximation algorithms
- Approximating maximum independent sets by excluding subgraphs
- Ultimate greedy approximation of independent sets in subcubic graphs
- Mining relevant information on the Web: a clique-based approach
- Approximation resistance from pairwise independent subgroups
- Simple and local independent set approximation
- Algorithm for optimal winner determination in combinatorial auctions
- Greedy approximations of independent sets in low degree graphs
- Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
- A heuristic algorithm for rainbow matchings and its application in rainbow Ramsey number for matchings
This page was built for publication: Approximation of independent sets in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4400840)
