Simple heuristics for unit disk graphs
From MaRDI portal
Publication:4698229
DOI10.1002/net.3230250205zbMath0821.90128arXivmath/9409226OpenAlexW2139349113WikidataQ56019093 ScholiaQ56019093MaRDI QIDQ4698229
S. S. Ravi, Heinz Breu, Harry B. III Hunt, Daniel J. Rosenkrantz, Madhav V. Marathe
Publication date: 12 June 1995
Published in: Networks (Search for Journal in Brave)
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)
Related Items (82)
Fair and square: cake-cutting in two dimensions ⋮ A randomized algorithm for online unit clustering ⋮ Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ On spectrum sharing games ⋮ Algorithms for Steiner Connected Dominating Set Problem Based on Learning Automata Theory ⋮ On dominating set of some subclasses of string graphs ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ A tight bound for online colouring of disk graphs ⋮ Faster approximation for maximum independent set on unit disk graph ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ Impact of locality on location aware unit disk graphs ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ 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 ⋮ Unnamed Item ⋮ Efficient independent set approximation in unit disk graphs ⋮ Binary programming formulations for the upper domination problem ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Local 7-coloring for planar subgraphs of unit disk graphs ⋮ Independent sets in Line of Sight networks ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Finding Large Independent Sets in Line of Sight Networks ⋮ Learning bounds via sample width for classifiers on finite metric spaces ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Note on coloring of double disk graphs ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Approximation algorithms for intersection graphs ⋮ Minimum clique partition in unit disk 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 ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ Approximating k-Connected m-Dominating Sets ⋮ Clustering the wireless ad hoc networks: a distributed learning automata approach ⋮ Computing inductive vertex orderings ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ 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 ⋮ Minimum vertex cover in ball graphs through local search ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ The within-strip discrete unit disk cover problem ⋮ Location-oblivious distributed unit disk graph coloring ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS ⋮ LOCAL CONSTRUCTION AND COLORING OF SPANNERS OF LOCATION AWARE UNIT DISK GRAPHS ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ Improper coloring of unit disk graphs ⋮ Dynamic graph coloring ⋮ On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ The number of disk graphs ⋮ Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles) ⋮ LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Domination in Geometric Intersection Graphs ⋮ 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 ⋮ In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS ⋮ Maximum scan statistics and channel assignment problems in homogeneous wireless networks ⋮ Hierarchically specified unit disk graphs ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ On the hardness of allocating frequencies for hybrid networks ⋮ Label placement by maximum independent set in rectangles ⋮ Hardness results and approximation algorithms of \(k\)-tuple domination in graphs ⋮ Unnamed Item ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ Unnamed Item ⋮ On-line coloring of geometric intersection graphs
Cites Work
This page was built for publication: Simple heuristics for unit disk graphs
