Modelling gateway placement in wireless networks: geometric k-centres of unit disc graphs
DOI10.1016/J.COMGEO.2010.12.003zbMATH Open1214.90022OpenAlexW2131625432MaRDI QIDQ543790FDOQ543790
Anna Lubiw, Stephane Durocher, Lata Narayanan, K. R. Jampani
Publication date: 17 June 2011
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2010.12.003
Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Discrete location and assignment (90B80)
Cites Work
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Improved Approximation Algorithms for Relay Placement
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
- Algorithm Theory - SWAT 2004
- A new approach to dynamic all pairs shortest paths
- Clustering to minimize the maximum intercluster distance
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- Efficient algorithms for centers and medians in interval and circular-arc graphs
- Routing with guaranteed delivery in ad hoc wireless networks
- On the Complexity of Some Common Geometric Location Problems
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Algorithms – ESA 2004
- Easy and hard bottleneck location problems
- Simple heuristics for unit disk graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- More planar two-center algorithms
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- The slab dividing approach to solve the Euclidean \(P\)-center problem
- A simple linear-time algorithm for computing the center of an interval graph
- An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths
- Efficient visibility queries in simple polygons
- On a circle placement problem
- On the computational complexity of centers locating in a graph
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
Cited In (4)
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- Sensor network topology design and analysis for efficient data gathering by a mobile mule
- Deployment optimization of multi-hop wireless networks based on substitution graph
- Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm
This page was built for publication: Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543790)
