Modelling gateway placement in wireless networks: geometric k-centres of unit disc graphs

DOI10.1016/J.COMGEO.2010.12.003MaRDI QIDQ543790zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, K. R. Jampani, Lata Narayanan, 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

zbMATH Keywords

facility locationintersection graphwireless networks\(k\)-centreunit disc graph

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Discrete location and assignment (90B80)

Recommendations

• scientific article; zbMATH DE number 2089212
• Covering Points by Unit Disks of Fixed Location
• Approximating \(k\)-center in planar graphs
• Minimum-cost coverage of point sets by disks
• A Best Possible Heuristic for the k-Center Problem

Cites work

• A new approach to dynamic all pairs shortest paths
• A simple linear-time algorithm for computing the center of an interval graph
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2004
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An improved algorithm for the p-center problem on interval graphs with unit lengths
• Clustering to minimize the maximum intercluster distance
• Easy and hard bottleneck location problems
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• Efficient visibility queries in simple polygons
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• More planar two-center algorithms
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• On a circle placement problem
• On the Complexity of Some Common Geometric Location Problems
• On the computational complexity of centers locating in a graph
• Routing with guaranteed delivery in ad hoc wireless networks
• Simple heuristics for unit disk graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths

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)