Journal of the ACM Bibliography
Avrim
Blum. New approximation algorithms for graph coloring. Journal
of the ACM, 41(3):470-516, May 1994.
[BibTeX entry]
Selected papers that cite this one
- N. Alon, P. Kelsen, S. Mahajan, and H. Ramesh. Approximate
Hypergraph Coloring Nordic Journal of Computing,
3(4):425-439, Winter 1996.
- 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.
- L. J. Cowen, W. Goddard, and C. E. Jesurum. Coloring with defect.
In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 548-557, New Orleans, Louisiana, 5-7 January
1997.
- Marc Demange, Pascal Grisoni, and Vangelis Th. Paschos. Differential
approximation algorithms for some combinatorial optimization
problems. Theoretical Computer Science,
209(1-2):107-122, 6 December 1998.
- 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.
- Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E.
Schapire, and Linda Sellie. Efficient learning of typical
finite automata from random walks. Information and
Computation, 138(1):23-48, 10 October 1997.
- David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by
semidefinite programming. Journal of the ACM,
45(2):246-265, March 1998.
Selected references
- 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.
- Avrim Blum. An
\tilde{O}(n^{0.4})-approximation algorithm for
3-coloring (and improved approximation algorithm for
k-coloring). In Proceedings of the Twenty First
Annual ACM Symposium on Theory of Computing, pages 535-542,
Seattle, Washington, 15-17 May 1989.
- Avrim Blum. Some
tools for approximate 3-coloring (extended abstract). In 31st
Annual Symposium on Foundations of Computer Science, volume II,
pages 554-562, St. Louis, Missouri, 22-24 October 1990. 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.
- Sundar Vishwanathan. Randomized online
graph coloring (preliminary version). In 31st Annual Symposium
on Foundations of Computer Science, volume II, pages 464-469, St.
Louis, Missouri, 22-24 October 1990. IEEE.
- Avi Wigderson. Improving the performance
guarantee for approximate graph coloring. Journal of the
ACM, 30(4):729-735, October 1983.
Shortcuts: