Minimum-diameter covering problems

DOI<147::AID-NET1>3.0.CO;2-M 10.1002/1097-0037(200010)36:3<147::AID-NET1>3.0.CO;2-MzbMath0973.05075OpenAlexW2089712558MaRDI QIDQ4520238

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<147::aid-net1>3.0.co;2-m

zbMATH Keywords

distanceNP-completeapproximation algorithmspolynomial time algorithmsgraph diametercovering problemsmultiple-choice

Mathematics Subject Classification ID

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

Related Items (12)

Group-based collective keyword querying in road networks ⋮ The approximation algorithms for a class of multiple-choice problem ⋮ Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods ⋮ Hardness results for homology localization ⋮ Unnamed Item ⋮ Parameterized complexity of team formation in social networks ⋮ Parameterized complexity of conflict-free set cover ⋮ Selecting and covering colored points ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Parameterized Complexity of Team Formation in Social Networks ⋮ ON RECTANGULAR COVERING PROBLEMS ⋮ Unnamed Item

Cites Work

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

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