Unit disk graphs
From MaRDI portal
Publication:1174134
DOI10.1016/0012-365X(90)90358-OzbMath0739.05079WikidataQ56210399 ScholiaQ56210399MaRDI QIDQ1174134
Charles J. Colbourn, Brent N. Clark, David S. Johnson
Publication date: 25 June 1992
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
On edge intersection graphs of paths with 2 bends ⋮ On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ Optimal gossiping in geometric radio networks in the presence of dynamical faults ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ On some applications of the selective graph coloring problem ⋮ Membrane computing to enhance time efficiency of minimum dominating set ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Algorithms for Steiner Connected Dominating Set Problem Based on Learning Automata Theory ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ On dominating set of some subclasses of string graphs ⋮ On Edge Intersection Graphs of Paths with 2 Bends ⋮ Approximating 2-cliques in unit disk graphs ⋮ Minimum-time aggregation scheduling in duty-cycled wireless sensor networks ⋮ Minimum Dominating Set Problem for Unit Disks Revisited ⋮ A tight bound for online colouring of disk graphs ⋮ Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ Structural parameterizations with modulator oblivion ⋮ Unnamed Item ⋮ Faster approximation for maximum independent set on unit disk graph ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ 1-extendability of independent sets ⋮ Complexity of edge monitoring on some graph classes ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Spanners for Directed Transmission Graphs ⋮ Unnamed Item ⋮ Efficient independent set approximation in unit disk graphs ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ On Local Structures of Cubicity 2 Graphs ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs ⋮ Independent sets in Line of Sight networks ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs ⋮ Improved solution to data gathering with mobile mule ⋮ Finding Large Independent Sets in Line of Sight Networks ⋮ On arrangements of orthogonal circles ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Learning bounds via sample width for classifiers on finite metric spaces ⋮ An improved distributed data aggregation scheduling in wireless sensor networks ⋮ Routing-efficient CDS construction in disk-containment graphs ⋮ Grid-Obstacle Representations with Connections to Staircase Guarding ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ On the speed of algebraically defined graph classes ⋮ On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ Dispersing and grouping points on planar segments ⋮ FAST METHOD FOR GENERATING RANDOM GEOMETRIC GRAPHS FOR WIRELESS NETWORKS MODELLING ⋮ PERFORMANCE ANALYSIS AND EVALUATION OF RANDOM WALK ALGORITHMS ON WIRELESS NETWORKS ⋮ MINIMUM LOCAL DISK COVER SETS FOR BROADCASTING IN HETEROGENEOUS MULTIHOP WIRELESS NETWORKS ⋮ Identifying and Locating–Dominating Codes in (Random) Geometric Networks ⋮ ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS ⋮ Unnamed Item ⋮ MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS ⋮ OVSF-CDMA code assignment in wireless ad hoc networks ⋮ On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon ⋮ Bounds on the size of the minimum dominating sets of some cylindrical grid graphs ⋮ A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET ⋮ Improper colouring of (random) unit disk graphs ⋮ Polynomial-time approximation schemes for piercing and covering with applications in wireless networks ⋮ Small 4-regular planar graphs that are not circle representable ⋮ Sphericity, cubicity, and edge clique covers of graphs ⋮ EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ 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 ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Facility location with tree topology and radial distance constraints ⋮ The number of disk graphs ⋮ LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS ⋮ The Complexity of Data Aggregation in Static and Dynamic Wireless Sensor Networks ⋮ Global Rigidity of Unit Ball Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Clique number and ball containment number of unit ball graphs ⋮ Connected Domination ⋮ ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ On some matching problems under the color-spanning model ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ A Survey of the Game “Lights Out!” ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Geometric red-blue set cover for unit squares and related problems ⋮ Shortest paths in intersection graphs of unit disks ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs ⋮ Improper Colourings of Unit Disk Graphs ⋮ Linear embeddings of graphs and graph limits
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unit disk graphs
- Some simplified NP-complete graph problems
- The NP-completeness column: an ongoing guide
- Universality considerations in VLSI circuits
- Planar Formulae and Their Uses
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Hamilton Paths in Grid Graphs
- The Location of Emergency Service Facilities
- The NP-completeness column: An ongoing guide
- The NP-completeness column: An ongoing guide
This page was built for publication: Unit disk graphs
