Analysing local algorithms in location-aware quasi-unit-disk graphs

DOI10.1016/j.dam.2011.05.004zbMath1228.05273OpenAlexW1965026568MaRDI QIDQ642985

Valentin Polishchuk, Marja Hassinen, Jukka Suomela, Joel Kaasinen, Andreas Wiese, Evangelos Kranakis

Publication date: 27 October 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.05.004

zbMATH Keywords

geometric graphslocal algorithmslocal horizonlocation-aware nodesquasi-unit-disk graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Modem illumination of monotone polygons ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Local approximability of max-min and min-max linear programs
• A simple local 3-approximation algorithm for vertex cover
• Local edge colouring of Yao-like subgraphs of unit disk graphs
• Die dichteste Packung von 36 Kreisen in einem Quadrat. (On the denest packing of 36 circles in a square)
• Unsolved problems in geometry
• Local 7-coloring for planar subgraphs of unit disk graphs
• Local solutions for global problems in wireless networks
• Survey of local algorithms
• Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
• Fast Distributed Approximations in Planar Graphs
• Computing Lightweight Spanners Locally
• Leveraging Linial’s Locality Limit
• The price of being near-sighted
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Locality in Distributed Graph Algorithms
• Local Labeling and Resource Allocation Using Preprocessing
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Distributed Computing: A Locality-Sensitive Approach
• 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
• What Can be Computed Locally?
• Distributed algorithms for edge dominating sets
• On the locality of bounded growth
• LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS
• Linear programming without the matrix
• Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• What cannot be computed locally!
• The Densest Packing of 9 Circles in a Square
• Local Algorithms for Edge Colorings in UDGs
• Constant-time distributed dominating set approximation

This page was built for publication: Analysing local algorithms in location-aware quasi-unit-disk graphs