An O(m n) algorithm for regular set-covering problems

DOI10.1016/0304-3975(87)90131-9zbMATH Open0632.68068OpenAlexW2051364416MaRDI QIDQ1095668FDOQ1095668

Authors: P. Bertolazzi, Antonio Sassano 

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90131-9

Recommendations

• An algorithm for set covering problem
• An approach to the solution of the set-covering problem
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• The set covering problem: Complexity, algorithms, experiments
• scientific article; zbMATH DE number 2102648

zbMATH Keywords

regular setsclutterspolynomial algorithms. optimal set-covering problemregular switching functionsthreshold synthesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites Work

• On the computational power of pushdown automata
• The matroids with the max-flow min-cut property
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Dualization of regular Boolean functions
• A Class of Polynomially Solvable Set-Covering Problems
• An Algorithm to Dualize a Regular Switching Function
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

• Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• Linear separation of connected dominating sets in graphs
• Dual-bounded generating problems: Weighted transversals of a hypergraph
• On the complexity of asymptotically optimal coverings and packings
• Interior and exterior functions of Boolean functions
• A characterization of knapsacks with the max-flow--min-cut property
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Reoptimization of set covering problems
• Boolean minors
• An inequality for polymatroid functions and its applications.
• Generating dual-bounded hypergraphs
• Computational aspects of monotone dualization: a brief survey
• Unique key Horn functions
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
• Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
• An algorithm for the difference between set covers

This page was built for publication: An O(m n) algorithm for regular set-covering problems

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