Cliques enumeration and tree-like resolution proofs
DOI10.1016/J.IPL.2018.03.001zbMATH Open1476.68112OpenAlexW2790492047WikidataQ61732571 ScholiaQ61732571MaRDI QIDQ1708271FDOQ1708271
Authors: Massimo Lauria 
Publication date: 5 April 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.03.001
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity of proofs (03F20)
Cites Work
- Fundamentals of parameterized complexity
- Reducibility among combinatorial problems
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Lower bounds based on the exponential time hypothesis
- Finding, minimizing, and counting weighted subgraphs
- On the complexity of \(k\)-SAT
- GRASP: a search algorithm for propositional satisfiability
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Concentration of Measure for the Analysis of Randomized Algorithms
- Short proofs are narrow—resolution made simple
- The intractability of resolution
- A combinatorial characterization of treelike resolution space
- A characterization of tree-like resolution size
- Parameterized bounded-depth Frege is not optimal
- Title not available (Why is that?)
- The Complexity of Propositional Proofs
- Space Complexity in Propositional Calculus
- The resolution complexity of independent sets and vertex covers in random graphs
- Near optimal seperation of tree-like and general resolution
- Space bounds for resolution
- Narrow proofs may be spacious, separating space and width in resolution
- A combinatorial characterization of resolution width
- Non-Ramsey graphs are \(c\log n\)-universal
- Clique is hard on average for regular resolution
- Parameterized Complexity of DPLL Search Procedures
- Optimality of size-width tradeoffs for resolution
- The Pebbling Problem is Complete in Polynomial Space
- Pebble games, proof complexity, and time-space trade-offs
- From small space to small width in resolution
- Title not available (Why is that?)
- The monotone complexity of \(k\)-clique on random graphs
Cited In (3)
Uses Software
This page was built for publication: Cliques enumeration and tree-like resolution proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708271)
