A note on the size of minimal covers

DOI10.1016/j.ipl.2006.10.012zbMath1184.68263OpenAlexW2128005025MaRDI QIDQ845985

Vaston Costa, Edward Hermann Haeusler, Loana Tito Nogueira, Eduardo Sany Laber

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.10.012

zbMATH Keywords

computational complexityBoolean functionsgraphstheory of computationvertex coverfinite combinatorial problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

\textsc{MAX MIN} vertex cover and the size of Betti tables ⋮ Counting the number of vertex covers in a trapezoid graph

Cites Work

• Unnamed Item
• Query strategies for priced information
• Complexity measures and decision tree complexity: a survey.
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• A new strategy for querying priced information
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• On the competitive ratio of evaluating priced functions