Journal of the ACM Bibliography

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms, Optimization, Theory

Additional Key Words and Phrases: Approximation algorithms, chromatic number, graph coloring, NP-completeness, randomized algorithms

Selected references

• Noga Alon and Nabil Kahale. A spectral technique for coloring random 3-colorable graphs (preliminary version). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 346-355, Montréal, Québec, Canada, 23-25 May 1994.

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

• Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 184-193, Montréal, Québec, Canada, 23-25 May 1994.

• Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470-516, May 1994.

• Avrim Blum and David Karger. An \tilde{O}(n^{3/14})-coloring algorithm for 3-colorable graphs. Information Processing Letters, 61(1):49-53, 14 January 1997.

• Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Coloring heuristics for register allocation. In Proceedings of the ACM SIGPLAN'89 Conference on Programming Language Design and Implementation (PLDI), pages 275-284, Portland, Oregon, 21-23 June 1989. SIGPLAN Notices 24(7), July 1989.

• Uriel Feige. Randomized graph products, chromatic numbers, and the Lovasz theta-function (extended abstract). In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 635-640, Las Vegas, Nevada, 29 May-1 June 1995.

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, March 1996.

• Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number (preliminary version). In Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, pages 278-287, Philadelphia, Pennsylvania, 24-27 May 1996. IEEE Computer Society Press.

• Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115-1145, November 1995.

• Magnús M. Halldórsson. Approximating the minimum maximal independence number. Information Processing Letters, 46(4):169-172, 25 June 1993.

• Johan Håstad. Clique is hard to approximate within n^{1 - epsilon}. In 37th Annual Symposium on Foundations of Computer Science, pages 627-636, Burlington, Vermont, 14-16 October 1996. IEEE.

• Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. In 35th Annual Symposium on Foundations of Computer Science, pages 819-830, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 286-293, San Diego, California, 16-18 May 1993.

• Sanjeev Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In 36th Annual Symposium on Foundations of Computer Science, pages 162-169, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• Mario Szegedy. A note on the Theta number of Lovász and the generalized Delsarte bound. In 35th Annual Symposium on Foundations of Computer Science, pages 36-39, Santa Fe, New Mexico, 20-22 November 1994. IEEE.

• Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, October 1983.

Shortcuts: