A Class of Polynomially Solvable Set-Covering Problems

DOI10.1137/0401031MaRDI QIDQ3834089zbMATH OpenOpenAlexFDO

Authors P. Bertolazzi, Antonio Sassano

Publication date 1988

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0401031

zbMATH Keywords

cluttermatroidmatroidal cluttersset-covering problem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Ideal clutters
• Intersecting restrictions in clutters
• On the facial structure of the set covering polytope
• On a certain class of nonideal clutters
• Clutter nonidealness

Cited in

(15)

• Polynomial-time algorithms for regular set-covering and threshold synthesis
• An O(m n) algorithm for regular set-covering problems
• A decomposition strategy for the vertex cover problem
• An O(nm)-time algorithm for computing the dual of a regular Boolean function
• A neural network for the minimum set covering problem
• An algorithm of polynomial order for computing the covering dimension of a finite space
• Boolean minors
• Testing idealness in the filter oracle model
• Intersecting and dense restrictions of clutters in polynomial time
• Clutter nonidealness
• Fractional packing in ideal clutters
• Partially Polynomial Kernels for Set Cover and Test Cover
• scientific article; zbMATH DE number 1354909 (Why is no real title available?)
• Intersecting and dense restrictions of clutters in polynomial time
• Bibliography on domination in graphs and some basic definitions of domination parameters

This page was built for publication: A Class of Polynomially Solvable Set-Covering Problems

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