Clique problem, cutting plane proofs and communication complexity

DOI10.1016/j.ipl.2012.07.003zbMath1248.68248arXiv1203.5414OpenAlexW2036953534MaRDI QIDQ456115

Stasys P. Jukna

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.5414

zbMATH Keywords

computational complexitycommunication complexityclique problemcutting plane proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Sorting in \(c \log n\) parallel steps
• The monotone circuit complexity of Boolean functions
• On cutting-plane proofs in combinatorial optimization
• A simple lower bound for monotone clique using a communication game
• The maximum edge biclique problem is NP-complete
• Short monotone formulae for the majority function
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On graphs with polynomially solvable maximum-weight clique problem
• Monotone circuits for matching require linear depth
• An upper bound for the number of maximal independent sets in a graph
• Parameterized Complexity of DPLL Search Procedures
• On cliques in graphs

This page was built for publication: Clique problem, cutting plane proofs and communication complexity