Approximation of independent sets in graphs. (English) Zbl 0903.05044
Jansen, Klaus (ed.) et al., Approximation algorithms for combinatorial optimization. International ICALP ’98 workshop, APPROX ’98, Aalborg, Denmark, July 18–19, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1444, 1-13 (1998).
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. … 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].
For the entire collection see [Zbl 0892.00051].
Reviewer: W.G.Brown (Montreal)
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C55 | Generalized Ramsey theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05D10 | Ramsey theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
