A note on the size of minimal covers

DOI10.1016/J.IPL.2006.10.012MaRDI QIDQ845985zbMATH OpenOpenAlexFDO

Authors Vaston Costa, Edward Hermann Haeusler, Eduardo S. Laber, Loana T. Nogueira

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 complexitygraphstheory of computationvertex coverBoolean functionsfinite 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)

Recommendations

• scientific article; zbMATH DE number 4110718
• scientific article; zbMATH DE number 822142
• Proof of covering minimality by generalizing the notion of independence
• Bounding the vertex cover number of a hypergraph
• Covering number product bounds size

Cites work

• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• A new strategy for querying priced information
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• Complexity measures and decision tree complexity: a survey.
• On the competitive ratio of evaluating priced functions
• Query strategies for priced information
• The critical complexity of all (monotone) boolean functions and monotone graph properties

Cited in

(10)

• Counting the number of vertex covers in a trapezoid graph
• scientific article; zbMATH DE number 221461 (Why is no real title available?)
• On the minimal cover property in \(\mathbf{ZF}\)
• scientific article; zbMATH DE number 165076 (Why is no real title available?)
• Minimum resolvable coverings with small parallel classes
• A note on small covers over cubes
• \textsc{MAX MIN} vertex cover and the size of Betti tables
• On the Size of Minimum Super Arrovian Domains
• A note on the core: minimal conversely consistent enlargement
• AN ERDŐS-KO-RADO THEOREM FOR MINIMAL COVERS

This page was built for publication: A note on the size of minimal covers

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