Simple heuristics for unit disk graphs
From MaRDI portal
Publication:4698229
Abstract: Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and to intersection graphs of higher dimensional regular objects.
Recommendations
- Graph-Theoretic Concepts in Computer Science
- Linear-time approximation algorithms for unit disk graphs
- scientific article; zbMATH DE number 2235058
- Plane hop spanners for unit disk graphs: simpler and better
- An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs
- Planar Hop Spanners for Unit Disk Graphs
- Plane hop spanners for unit disk graphs
- Near-optimal algorithms for shortest paths in weighted unit-disk graphs
- Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs.
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 17824 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- On the hardness of approximating minimization problems
Cited in
(92)- Local construction and coloring of spanners of location aware unit disk graphs
- Annulus graphs in \(\mathbb{R}^d\)
- A tight bound for online colouring of disk graphs
- A randomized algorithm for online unit clustering
- Location-oblivious distributed unit disk graph coloring
- A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
- Good Quality Virtual Realization of Unit Ball Graphs
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- Fair and square: cake-cutting in two dimensions
- Local 7-coloring for planar subgraphs of unit disk graphs
- A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
- Algorithms for Steiner connected dominating set problem based on learning automata theory
- Maximum area independent sets in disk intersection graphs
- Improper coloring of unit disk graphs
- scientific article; zbMATH DE number 7650099 (Why is no real title available?)
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
- Computing inductive vertex orderings
- On spectrum sharing games
- Label placement by maximum independent set in rectangles
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- On the hardness of allocating frequencies for hybrid networks
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs
- A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
- Good quality virtual realization of unit disk graphs
- Finding large independent sets in line of sight networks
- On forbidden induced subgraphs for unit disk graphs
- Plane hop spanners for unit disk graphs: simpler and better
- Hierarchically specified unit disk graphs
- On dominating set of some subclasses of string graphs
- Online dominating set and coloring
- Approximation algorithms for maximum independent set of pseudo-disks
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- On-line coloring of geometric intersection graphs
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- In-place algorithms for computing a largest clique in geometric intersection graphs
- Algorithmic aspects of secure domination in unit disk graphs
- Total (restrained) domination in unit disk graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Maximum scan statistics and channel assignment problems in homogeneous wireless networks
- scientific article; zbMATH DE number 2235058 (Why is no real title available?)
- Impact of locality on location aware unit disk graphs
- Approximation Algorithms for Geometric Intersection Graphs
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- Dynamic graph coloring
- scientific article; zbMATH DE number 2230206 (Why is no real title available?)
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Binary programming formulations for the upper domination problem
- Note on coloring of double disk graphs
- Approximation algorithms for intersection graphs
- Efficient independent set approximation in unit disk graphs
- An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
- Graph-Theoretic Concepts in Computer Science
- Minimum dominating set problem for unit disks revisited
- Domination in Geometric Intersection Graphs
- Improved algorithm for maximum independent set on unit disk graph
- Minimum clique partition in unit disk graphs
- Approximation algorithms for maximum independent set of a unit disk graph
- Faster approximation for maximum independent set on unit disk graph
- Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- Clustering the wireless ad hoc networks: a distributed learning automata approach
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Perfectness and imperfectness of unit disk graphs on triangular lattice points
- Approximating minimum independent dominating sets in wireless networks
- The number of disk graphs
- Distributed minimum dominating set approximations in restricted families of graphs
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- Finding minimum weight connected dominating set in stochastic graph based on learning automata
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Minimum vertex cover in ball graphs through local search
- Local edge colouring of Yao-like subgraphs of unit disk graphs
- Approximating k-Connected m-Dominating Sets
- On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks
- Learning bounds via sample width for classifiers on finite metric spaces
- Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
- Linear-time approximation algorithms for unit disk graphs
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- scientific article; zbMATH DE number 7121835 (Why is no real title available?)
- Efficient distributed algorithms for topology control problem with shortest path constraints
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Distributed connected dominating sets in unit square and disk graphs
- A survey on variant domination problems in geometric intersection graphs
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- Independent sets in Line of Sight networks
- Semi-total domination in unit disk graphs
- On the hardness of allocating frequencies for hybrid networks
- Locating battery charging stations to facilitate almost shortest paths
- The within-strip discrete unit disk cover problem
This page was built for publication: Simple heuristics for unit disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4698229)
