|
|||||
|
|
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs |
|
| Authors: | Paul Beame Russell Impagliazzo Ashish Sabharwal |
| Affiliation: | (1) Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195-2350, USA;(2) Computer Science and Engineering, University of California, San Diego, La Jolla, CA 92093-0114, USA;(3) Present address: Department of Computer Science, Cornell University, Ithaca, NY 14853-7501, USA |
| Abstract: | |
| Keywords: | Resolution proof complexity hardness of approximation independent set vertex cover |
| 本文献已被 SpringerLink 等数据库收录！ | |