Simple heuristics for unit disk graphs
From MaRDI portal
Publication:4698229
DOI10.1002/NET.3230250205zbMATH Open0821.90128DBLPjournals/networks/MaratheBHRR95arXivmath/9409226OpenAlexW2139349113WikidataQ56019093 ScholiaQ56019093MaRDI QIDQ4698229FDOQ4698229
H. B. III Hunt, S. S. Ravi, Heinz Breu, Daniel J. Rosenkrantz, Madhav V. Marathe
Publication date: 12 June 1995
Published in: Networks (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/math/9409226
maximum independent setminimum coloringminimum vertex coverunit disk graphsminimum dominating seton-line coloring heuristic
Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
Cited In (89)
- A tight bound for online colouring of disk graphs
- A randomized algorithm for online unit clustering
- Location-oblivious distributed unit disk graph coloring
- Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
- 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
- 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
- Improper coloring of unit disk graphs
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
- On spectrum sharing games
- Label placement by maximum independent set in rectangles
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
- On the hardness of allocating frequencies for hybrid networks
- On forbidden induced subgraphs for unit disk graphs
- Plane hop spanners for unit disk graphs: simpler and better
- Hierarchically specified unit disk graphs
- 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
- A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET
- 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
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Maximum scan statistics and channel assignment problems in homogeneous wireless networks
- Impact of locality on location aware unit disk graphs
- Dynamic graph coloring
- Approximation Algorithms for Geometric Intersection Graphs
- Title not available (Why is that?)
- LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS
- EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS
- MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Efficient independent set approximation in unit disk graphs
- Domination in Geometric Intersection Graphs
- Note on coloring of double disk graphs
- Approximation algorithms for intersection graphs
- An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
- LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS
- Minimum clique partition in unit disk graphs
- Faster approximation for maximum independent set on unit disk graph
- Approximation algorithms for maximum independent set of a unit disk graph
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Clustering the wireless ad hoc networks: a distributed learning automata approach
- 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
- Approximating k-Connected m-Dominating Sets
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- Approximation algorithms for the connected sensor cover problem
- Minimum vertex cover in ball graphs through local search
- Local edge colouring of Yao-like subgraphs of unit disk graphs
- Learning bounds via sample width for classifiers on finite metric spaces
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
- Title not available (Why is that?)
- Minimum Dominating Set Problem for Unit Disks Revisited
- Locating battery charging stations to facilitate almost shortest paths
- The within-strip discrete unit disk cover problem
- Annulus graphs in \(\mathbb{R}^d\)
- Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs
- Fair and square: cake-cutting in two dimensions
- Title not available (Why is that?)
- Linear-Time Approximation Algorithms for Unit Disk Graphs
- Computing inductive vertex orderings
- Online dominating set and coloring
- On dominating set of some subclasses of string graphs
- Algorithmic aspects of secure domination in unit disk graphs
- Total (restrained) domination in unit disk graphs
- Algorithms for Steiner Connected Dominating Set Problem Based on Learning Automata Theory
- Finding Large Independent Sets in Line of Sight Networks
- Binary programming formulations for the upper domination problem
- On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks
- Improved Algorithm for Maximum Independent Set on Unit Disk Graph
- Distributed connected dominating sets in unit square and disk graphs
- Title not available (Why is that?)
- A survey on variant domination problems in geometric intersection graphs
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Semi-total domination in unit disk graphs
- Independent sets in Line of Sight networks
- On the hardness of allocating frequencies for hybrid networks
Recommendations
- Title not available (Why is that?) 👍 👎
- Graph-Theoretic Concepts in Computer Science 👍 👎
- Plane hop spanners for unit disk graphs: simpler and better 👍 👎
- Near-optimal algorithms for shortest paths in weighted unit-disk graphs 👍 👎
- Plane hop spanners for unit disk graphs 👍 👎
- Linear-Time Approximation Algorithms for Unit Disk Graphs 👍 👎
- Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. 👍 👎
- Planar Hop Spanners for Unit Disk Graphs 👍 👎
- An optimal algorithm for \(L_1\) shortest paths in unit-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)
