Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655098 | Discrete Applied Mathematics | 2005 | 23 Pages |
Abstract
These proof complexity bounds imply that many natural algorithms for k-coloring or k-colorability have essentially the same exponential tradeoff lower bounds on their running times. We also show that very simple algorithms for k-colorability have upper bounds on their running times that are qualitatively similar to the lower bounds as a function of the graph density.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore,