Minimum-diameter covering problems

DOI10.1002/1097-0037(200010)36:3%3C147::AID-NET1%3E3.0.CO;2-MMaRDI QIDQ4520238zbMATH OpenOpenAlexFDO

Authors Esther M. Arkin, Refael Hassin

Publication date 3 December 2001

Full work available at URL https://doi.org/10.1002/1097-0037(200010)36:3%3C147::aid-net1%3E3.0.co;2-m

zbMATH Keywords

approximation algorithmscovering problemsdistancegraph diametermultiple-choiceNP-completepolynomial time algorithms

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Polynomial time approximation schemes for minimum disk cover problems
• Generalized submodular cover problems and applications
• Heuristic and Special Case Algorithms for Dispersion Problems
• Computing minimum diameter color-spanning sets
• On minimum sum of radii and diameters clustering

Cites work

• Approximating the tree and tour covers of a graph
• Clustering to minimize the maximum intercluster distance
• Fast Approximation Algorithms for Knapsack Problems
• Generalized p-center problems: Complexity results and approximation algorithms
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Obnoxious Facility Location on Graphs
• On the Complexity of Timetable and Multicommodity Flow Problems
• Some Matching Problems for Bipartite Graphs
• The linear multiple choice knapsack problem
• The Multiple-Choice Knapsack Problem
• The NP-completeness column: An ongoing guide

Cited in

(16)

• Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
• Parameterized complexity of team formation in social networks
• Selecting and covering colored points
• An optimal algorithm for the minimum disc cover problem
• Parameterized complexity of team formation in social networks
• scientific article; zbMATH DE number 5936584 (Why is no real title available?)
• On rectangular covering problems
• Group-based collective keyword querying in road networks
• The approximation algorithms for a class of multiple-choice problem
• Min-Power Covering Problems
• Network optimization on partitioned pairs of points
• scientific article; zbMATH DE number 7662164 (Why is no real title available?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Parameterized complexity of conflict-free set cover
• Parameterized complexity of geometric covering problems having conflicts
• Hardness results for homology localization

This page was built for publication: Minimum-diameter covering problems

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