Analysing local algorithms in location-aware quasi-unit-disk graphs
From MaRDI portal
Publication:642985
DOI10.1016/J.DAM.2011.05.004zbMATH Open1228.05273OpenAlexW1965026568MaRDI QIDQ642985FDOQ642985
Authors: Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, Andreas Wiese 
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
Recommendations
- Impact of locality on location aware unit disk graphs
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- Local construction and coloring of spanners of location aware unit disk graphs
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Unsolved problems in geometry
- Locality in Distributed Graph Algorithms
- What cannot be computed locally!
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Minimum dominating set approximation in graphs of bounded arboricity
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Constant-time distributed dominating set approximation
- 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
- Cross-layer design of control over wireless networks
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Survey of local algorithms
- On the locality of bounded growth
- Linear programming without the matrix
- Die dichteste Packung von 36 Kreisen in einem Quadrat. (On the denest packing of 36 circles in a square)
- Title not available (Why is that?)
- The Densest Packing of 9 Circles in a Square
- Local solutions for global problems in wireless networks
- The price of being near-sighted
- A simple local 3-approximation algorithm for vertex cover
- What Can be Computed Locally?
- Distributed algorithms for edge dominating sets
- Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
- Local edge colouring of Yao-like subgraphs of unit disk graphs
- Local 7-coloring for planar subgraphs of unit disk graphs
- Computing Lightweight Spanners Locally
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Local Labeling and Resource Allocation Using Preprocessing
- Title not available (Why is that?)
- Local construction and coloring of spanners of location aware unit disk graphs
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- Local Algorithms for Edge Colorings in UDGs
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Local approximability of max-min and min-max linear programs
Cited In (6)
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Distributed coloring and the local structure of unit-disk graphs
- Modem illumination of monotone polygons
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Distributed coloring and the local structure of unit-disk graphs
- Analysing local algorithms in location-aware quasi-unit-disk graphs
This page was built for publication: Analysing local algorithms in location-aware quasi-unit-disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q642985)
