Analysing local algorithms in location-aware quasi-unit-disk graphs
From MaRDI portal
Publication:642985
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
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
