The connected disk covering problem

DOI10.1007/s10878-017-0195-0zbMath1393.90105OpenAlexW2766322406MaRDI QIDQ1702836

Binhai Zhu, Yi Xu, Wencheng Wang, Ji-Gen Peng

Publication date: 1 March 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0195-0

zbMATH Keywords

computational geometryfacility location problemunit disk graphs\(K\)-center problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Orientational variable-length strip covering problem: a branch-and-price-based algorithm

Cites Work

• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Efficient algorithm for placing a given number of base stations to cover a convex region
• Clustering to minimize the maximum intercluster distance
• Unit disk graphs
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• Some variations on constrained minimum enclosing circle problem
• An approximation algorithm for \(k\)-center problem on a convex polygon
• Computing the Line-Constrained k-center in the Plane for Small k
• On the Complexity of Some Common Geometric Location Problems
• The p-Centre Problem-Heuristic and Optimal Algorithms
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• A Best Possible Heuristic for the k-Center Problem