Set multi-covering via inclusion-exclusion

DOI10.1016/j.tcs.2009.05.020zbMath1171.68048OpenAlexW1998894154MaRDI QIDQ837180

Yuexuan Wang, Qiang-Sheng Hua, Dongxiao Yu, Francis C. M. Lau

Publication date: 10 September 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.020

zbMATH Keywords

complexityalgorithminclusion-exclusionset multi-covering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (4)

MLQCC: an improved local search algorithm for the set k‐covering problem ⋮ Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis ⋮ Robust multicovers with budgeted uncertainty ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems

Cites Work

• Unnamed Item
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Dynamic programming meets the principle of inclusion and exclusion
• A threshold of ln n for approximating set cover
• The Travelling Salesman Problem in Bounded Degree Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

This page was built for publication: Set multi-covering via inclusion-exclusion