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

DOI10.1016/J.COMGEO.2010.12.003zbMATH Open1214.90022OpenAlexW2131625432MaRDI QIDQ543790FDOQ543790

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

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

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)

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)