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