Greed is good: Approximating independent sets in sparse and bounded-degree graphs

N. Alon, U. Feige, A. Wigderson, and D. Zuckerman. Derandomized graph products.Computational Complexity, 5 (1): 60–75, 1995.

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems.Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, pages 14–23, Oct. 1992.

P. Berman and T. Fujito. On the approximation properties of the independent set problem in degree 3 graphs.Proc. Fourth Workshop on Algorithms and Data Structures pages 449–460. LNCS #955, Springer-Verlag, Berlin, 1995.

P. Berman and M. Fürer. Approximating maximum independent set in bounded degree graphs.Proc. Fifth Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 365–371, Jan. 1994.

R. L. Brooks. On coloring the nodes of a network.Math. Proc. Cambridge Philos. Soc., 37: 194–197, 1991.

V. Chvátal.Linear Programming. Freeman, New York, 1983.

V. Chvátal and C. McDiarmid. Small transversals in hypergraphs.Combinatorica, 12 (1): 19–26, 1992.

P. Erdős. On the graph theorem of Turán (in Hungarian).Mat. Lapok 21: 249–251, 1970.

A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs.SIAM J. Discrete Math., 1 (4): 434–446, No. 1988.

J. R. Griggs. Lower bounds on the independence number in terms of the degrees.J. Combin. Theory Ser. B, 34: 22–39, 1983.

M. M. Halldórsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs.Proc. Fourth Scand. Workshop on Algorithm Theory, pages 195–206. LNCS #824, Springer-Verlag, Berlin, 1994.

M. M. Halldórsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree via subgraph removal.Nordic J. Comput., 1 (4): 475–492, 1994.

M. M. Halldórsson and K. Yoshihara. Greedy approximations of independent sets in low degree graphs.Proc. Sixth Internat. Symp. on Algorithms and Computation, pages 152–161. LNCS #1004, Springer-Verlag, Berlin, Dec. 1995.

D. S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems.Discrete Appl. Math., 6: 243–254, 1983.

J. Hopcroft and R. Karp. Ann 5/2 algorithm for maximal matchings in bipartite graphs.SIAM J. Comput., 4: 225–231, 1973.

D. S. Johnson. Worst case behavior of graph coloring algorithms.Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pages 513–527. Congressus Numerantium, X, Utilitas Math., Winnipeg, Manitoba, 1974.

R. Karp and V. Ramachandran. A survey of parallel algorithms for shared-memory machines. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, volume A, Chapter 17, pages 869–941. Elsevier, Amsterdam, 1990.

S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computational views of approximability.Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science, pages 819–830, 1994.

E. Kubicka, G. Kubicki, and D. Kountanis. Approximation algorithms for the chromatic sum.Proc. 1st Great Lakes Computer Science Conf. LNCS #507, Springer-Verlag, Berlin, Oct. 1989.

E. Lawler.Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.

N. Linial. Locality in distributive algorithms.SIAM J. Comput., 21: 193–201, 1992.

L. Lovász. Three short proofs in graph theory.J. Combin. Theory Ser. B, 19: 269–271, 1975.

C. McDiarmid. Colouring random graphs.Ann. Oper. Res., 1: 183–200, 1984.

G. L. Nemhauser and L. Trotter. Vertex packings Structural properties and algorithms.Math. Programming, 8: 232–248, 1975.

C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes.J. Comput. System Sci., 43: 425–440, 1991.

J. B. Shearer. A note on the independence number of triangle-free graphs.Discrete Math., 46: 83–87, 1983.

H. U. Simon. On approximate solutions for combinatorial optimization problems.SIAM J. Discrete Math., 3 (2): 294–310, May 1990.

P. Turán. On an extremal problem in graph theory (in Hungarian).Mat. Fiz. Lapok, 48: 436–452, 1941.

Twentieth Century Fox.Wall Street. Motion picture, 1987.

V. K. Wei. A lower bound on the stability number of a simple graph. Technical Memorandum No. 81-11217-9, Bell Laboratories, 1981.