Budgeted maximum graph coverage

DOI10.1007/3-540-36379-3_28MaRDI QIDQ4414508zbMATH OpenFDO

Authors Diana Poensgen, S. S. Ravi, Sven O. Krumke, Madhav V. Marathe, H.-C. Wirth

Publication date 25 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730321.htm

zbMATH Keywords

approximation algorithmbudgeted maximum coverageinteger linear programmingmaximum weight matchingtreewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• The budgeted maximum coverage problem
• Maximal covering tree problems
• An approximation algorithm for maximum weight budgeted connected set cover
• scientific article; zbMATH DE number 6851883
• Partial vertex cover and budgeted maximum coverage in bipartite graphs

Cited in

(7)

• The budgeted maximum coverage problem
• Approximations for restrictions of the budgeted and generalized maximum coverage problems
• An approximation algorithm for maximum weight budgeted connected set cover
• Maximum weighted independent sets with a budget
• Phylogenetic diversity and the maximum coverage problem
• The generalized maximum coverage problem
• An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees

This page was built for publication: Budgeted maximum graph coverage

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