VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

DOI10.1142/S0129054108005747MaRDI QIDQ3526982zbMATHFDO

Authors Sasanka Roy, Sandip Das, Gautam K. Das, Subhas C. Nandy

Publication date 25 September 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexityapproximation algorithmwireless networkcovering problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Network design and communication in computer systems (68M10) Discrete location and assignment (90B80)

Recommendations

• Base station placement on boundary of a convex polygon
• Distributed Computing – IWDC 2005
• Efficient algorithm for placing a given number of base stations to cover a convex region
• scientific article; zbMATH DE number 2089212
• Polynomial time approximation schemes for base station coverage with minimum total radii

Cites work

• scientific article; zbMATH DE number 1033560 (Why is no real title available?)
• A Best Possible Heuristic for the k-Center Problem
• A heuristic for the p-center problem in graphs
• A near-linear algorithm for the planar 2-center problem
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• More planar two-center algorithms
• Polynomial time approximation schemes for base station coverage with minimum total radii
• The searching over separators strategy to solve some NP-hard problems in subexponential time

Cited in

(18)

• Worst-case optimal covering of rectangles by disks
• scientific article; zbMATH DE number 1629974 (Why is no real title available?)
• THE ALIGNED K-CENTER PROBLEM
• An incremental version of the \(k\)-center problem on boundary of a convex polygon
• Base Location Problems for Base-Monotone Regions
• Base station placement on boundary of a convex polygon
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• Solving the natural wireless localization problem to optimality efficiently
• scientific article; zbMATH DE number 2089212 (Why is no real title available?)
• Covering convex polygons by two congruent disks
• Constrained \(k\)-center problem on a convex polygon
• Covering convex polygons by two congruent disks
• Efficient algorithm for placing a given number of base stations to cover a convex region
• Distributed Computing – IWDC 2005
• An approximation algorithm for \(k\)-center problem on a convex polygon
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• The connected disk covering problem
• Range assignment of base-stations maximizing coverage area without interference

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

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