Some tools for approximate 3-coloring
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- A better performance guarantee for approximate graph coloringAlgorithmica, 1990
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- An O(n0.4)-approximation algorithm for 3-coloringPublished by Association for Computing Machinery (ACM) ,1989
- Almost all k-colorable graphs are easy to colorJournal of Algorithms, 1988
- Generating quasi-random sequences from semi-random sourcesJournal of Computer and System Sciences, 1986
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sourcesPublished by Association for Computing Machinery (ACM) ,1985
- Unbiased bits from sources of weak randomness and probabilistic communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Random polynomial time is equal to slightly-random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983