Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
From MaRDI portal
Publication:543790
DOI10.1016/j.comgeo.2010.12.003zbMath1214.90022OpenAlexW2131625432MaRDI QIDQ543790
Stephane Durocher, Lata Narayanan, K. R. Jampani, Anna Lubiw
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)
Related Items (4)
Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Deployment optimization of multi-hop wireless networks based on substitution graph
Cites Work
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths
- Clustering to minimize the maximum intercluster distance
- On a circle placement problem
- Easy and hard bottleneck location problems
- Unit disk graphs
- The slab dividing approach to solve the Euclidean \(P\)-center problem
- Unit disk graph recognition is NP-hard
- Efficient visibility queries in simple polygons
- More planar two-center algorithms
- On the Complexity of Some Common Geometric Location Problems
- A simple linear-time algorithm for computing the center of an interval graph
- Improved Approximation Algorithms for Relay Placement
- Worst-case update times for fully-dynamic all-pairs shortest paths
- 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
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- On the computational complexity of centers locating in a graph
- Efficient algorithms for centers and medians in interval and circular-arc graphs
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Simple heuristics for unit disk graphs
- Algorithm Theory - SWAT 2004
- A new approach to dynamic all pairs shortest paths
- Algorithms – ESA 2004
- Routing with guaranteed delivery in ad hoc wireless networks
This page was built for publication: Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
