A note on the size of minimal covers
From MaRDI portal
Publication:845985
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
computational complexityBoolean functionsgraphstheory of computationvertex coverfinite combinatorial problems
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