On the query complexity of clique size and maximum satisfiability

DOI10.1006/JCSS.1996.0070MaRDI QIDQ1816736zbMATH OpenOpenAlexFDO

Authors Richard Chang

Publication date 31 March 1997

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1996.0070

zbMATH Keywords

bounded query complexityClique Sizemaximum clique

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the approximability of clique and related maximization problems
• On the maximum quasi-clique problem
• scientific article; zbMATH DE number 1424314
• Cliques, colouring and satisfiability: from structure to algorithms
• On hardness of approximating the parameterized clique problem
• On the complexity of fixed parameter clique and dominating set
• Algorithmic lower bounds for problems parameterized by clique-width
• On the maximal clique problem

Cited in

(3)

• Bounded queries, approximations, and the Boolean hierarchy
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

This page was built for publication: On the query complexity of clique size and maximum satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1816736)