An O(m n) algorithm for regular set-covering problems
From MaRDI portal
Publication:1095668
DOI10.1016/0304-3975(87)90131-9zbMath0632.68068OpenAlexW2051364416MaRDI QIDQ1095668
Antonio Sassano, Paola Bertolazzi
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
regular setsclutterspolynomial algorithms. optimal set-covering problemregular switching functionsthreshold synthesis
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (14)
An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function ⋮ Dual-bounded generating problems: Weighted transversals of a hypergraph ⋮ Boolean minors ⋮ Interior and exterior functions of Boolean functions ⋮ Unique key Horn functions ⋮ Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation ⋮ An inequality for polymatroid functions and its applications. ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ A characterization of knapsacks with the max-flow--min-cut property ⋮ Generating dual-bounded hypergraphs ⋮ Linear separation of connected dominating sets in graphs ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dualization of regular Boolean functions
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- The matroids with the max-flow min-cut property
- On the computational power of pushdown automata
- A Class of Polynomially Solvable Set-Covering Problems
- An Algorithm to Dualize a Regular Switching Function
This page was built for publication: An O(m n) algorithm for regular set-covering problems
