Approximate graph coloring by semidefinite programming
Authors:
- D. KargerDKD. Karger
- R. MotwaniRMR. Motwani
- M. SudanMSM. Sudan
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2-13
Abstract
No abstract availableThis publication has 23 references indexed in Scilit:
- On Syntactic versus Computational Views of ApproximabilitySIAM Journal on Computing, 1998
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial OptimizationSIAM Journal on Optimization, 1995
- New approximation algorithms for graph coloringJournal of the ACM, 1994
- A still better performance guarantee for approximate graph coloringInformation Processing Letters, 1993
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- Forbidden intersectionsTransactions of the American Mathematical Society, 1987
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- Register allocation via coloringComputer Languages, 1981
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- A technique for colouring a graph applicable to large scale timetabling problemsThe Computer Journal, 1969