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)- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- On spectrum sharing games
- Hierarchically specified unit disk graphs
- Clustering the wireless ad hoc networks: a distributed learning automata approach
- Minimum vertex cover in ball graphs through local search
- In-place algorithms for computing a largest clique in geometric intersection graphs
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Impact of locality on location aware unit disk graphs
- Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- Minimum dominating set problem for unit disks revisited
- ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
- Minimum clique partition in unit disk graphs
- Perfectness and imperfectness of unit disk graphs on triangular lattice points
- Good Quality Virtual Realization of Unit Ball Graphs
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Local construction and coloring of spanners of location aware unit disk graphs
- A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Label placement by maximum independent set in rectangles
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
- On-line coloring of geometric intersection graphs
- Efficient distributed algorithms for topology control problem with shortest path constraints
- A tight bound for online colouring of disk graphs
- Dynamic graph coloring
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Distributed minimum dominating set approximations in restricted families of graphs
- Approximating minimum independent dominating sets in wireless networks
- Local edge colouring of Yao-like subgraphs of unit disk graphs
- Faster approximation for maximum independent set on unit disk graph
- Graph-Theoretic Concepts in Computer Science
- The number of disk graphs
- Maximum area independent sets in disk intersection graphs
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Maximum scan statistics and channel assignment problems in homogeneous wireless networks
- Locating battery charging stations to facilitate almost shortest paths
- Finding minimum weight connected dominating set in stochastic graph based on learning automata
- Efficient independent set approximation in unit disk graphs
- Learning bounds via sample width for classifiers on finite metric spaces
- Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- On forbidden induced subgraphs for unit disk graphs
- Approximating k-Connected m-Dominating Sets
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- A self-stabilizing distributed approximation algorithm for the minimum connected dominating set
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- A randomized algorithm for online unit clustering
- A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
- Approximation Algorithms for Geometric Intersection Graphs
- Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
- Improper coloring of unit disk graphs
- Local 7-coloring for planar subgraphs of unit disk graphs
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Approximation algorithms for maximum independent set of a unit disk graph
- The within-strip discrete unit disk cover problem
- Plane hop spanners for unit disk graphs: simpler and better
- Approximation algorithms for maximum independent set of pseudo-disks
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
- Location-oblivious distributed unit disk graph coloring
- Domination in Geometric Intersection Graphs
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- scientific article; zbMATH DE number 2230206 (Why is no real title available?)
- On the hardness of allocating frequencies for hybrid networks
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- Note on coloring of double disk graphs
- Approximation algorithms for intersection graphs
- Fair and square: cake-cutting in two dimensions
- Computing inductive vertex orderings
- On dominating set of some subclasses of string graphs
- Algorithmic aspects of secure domination in unit disk graphs
- Annulus graphs in \(\mathbb{R}^d\)
- Distributed connected dominating sets in unit square and disk graphs
- Semi-total domination in unit disk graphs
- scientific article; zbMATH DE number 7121835 (Why is no real title available?)
- Online dominating set and coloring
- Independent sets in Line of Sight networks
- scientific article; zbMATH DE number 2235058 (Why is no real title available?)
- Total (restrained) domination in unit disk graphs
- Linear-time approximation algorithms for unit disk graphs
- scientific article; zbMATH DE number 7650099 (Why is no real title available?)
- A survey on variant domination problems in geometric intersection graphs
- Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
- On the hardness of allocating frequencies for hybrid networks
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- Improved algorithm for maximum independent set on unit disk graph
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Binary programming formulations for the upper domination problem
- Algorithms for Steiner connected dominating set problem based on learning automata theory
- Good quality virtual realization of unit disk graphs
- Finding large independent sets in line of sight networks
- On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks
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)
