The connected disk covering problem

DOI10.1007/S10878-017-0195-0MaRDI QIDQ1702836zbMATH OpenOpenAlexFDO

Authors Yi Xu, Wencheng Wang, Binhai Zhu, 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)

Recommendations

• Constrained \(k\)-center problem on a convex polygon
• scientific article; zbMATH DE number 1696646
• An approximation algorithm for \(k\)-center problem on a convex polygon
• Covering and piercing disks with two centers
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

Cites work

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

Cited in

(3)

• Constrained \(k\)-center problem on a convex polygon
• Orientational variable-length strip covering problem: a branch-and-price-based algorithm
• An approximation algorithm for \(k\)-center problem on a convex polygon

This page was built for publication: The connected disk covering problem

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