The resolution complexity of independent sets and vertex covers in random graphs
From MaRDI portal
Publication:2474203
DOI10.1007/s00037-007-0230-0zbMath1137.68030MaRDI QIDQ2474203
Ashish Sabharwal, Russell Impagliazzo, P. W. Beame
Publication date: 5 March 2008
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-007-0230-0
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
03F20: Complexity of proofs
Related Items
Unnamed Item, Constructing concrete hard instances of the maximum independent set problem, Parameterized Complexity of DPLL Search Procedures, Cutting planes cannot approximate some integer programs, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Cliques enumeration and tree-like resolution proofs, Large clique is hard on average for resolution, Limitations of restricted branching in clause learning, Parameterized Bounded-Depth Frege Is Not Optimal