Unit disk graphs

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)

zbMATH Keywords

algorithmsintersection graphunit disk graphpoints in the plane

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

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

Related Items (only showing first 100 items - show all)

Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Unnamed Item ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Binary programming formulations for the upper domination problem ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Bottleneck matching in the plane ⋮ Minimum weight clustered dominating tree problem ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ Computing maximum matchings in temporal graphs ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Proper colorability of segment intersection graphs ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Covering random points in a unit disk ⋮ 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 ⋮ Theoretical Aspects of Graph Models for MANETs ⋮ Approximating k-Connected m-Dominating Sets ⋮ Compact Routing in Unit Disk Graphs ⋮ The wake up dominating set problem ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Hierarchically specified unit disk graphs ⋮ 1-extendability of independent sets ⋮ On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks ⋮ Energy-Efficient Dominating Tree Construction in Wireless Ad Hoc and Sensor Networks ⋮ Contact graphs of boxes with unidirectional contacts ⋮ Bipartite graphs of small readability ⋮ Collaborative broadcast in \(\mathcal{O}(\log \log n)\) rounds ⋮ A survey on variant domination problems in geometric intersection graphs ⋮ Maximum bipartite subgraphs of geometric intersection graphs ⋮ Computing a maximum clique in geometric superclasses of disk graphs ⋮ Complexity results on \(k\)-independence in some graph products ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Domination in Geometric Intersection Graphs ⋮ Online dominating set and coloring ⋮ On the complexity of target set selection in simple geometric networks ⋮ Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier ⋮ Generalizing Geometric Graphs ⋮ Total (restrained) domination in unit disk graphs ⋮ Approximating the probabilistic \(p\)-center problem under pressure ⋮ Domination polynomials of the grid, the cylinder, the torus, and the king graph ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Integer linear programming models and greedy heuristic for the minimum weighted independent dominating set problem ⋮ Maximum independent and disjoint coverage ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Unnamed Item ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ Unnamed Item ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ On Covering Segments with Unit Intervals ⋮ On the minimum and maximum selective graph coloring problems in some graph classes ⋮ On pseudo-disk hypergraphs ⋮ Minimum ply covering of points with disks and squares ⋮ CPG graphs: some structural and hardness results ⋮ Connectivity of soft random geometric graphs over annuli ⋮ The connected domination number of grids ⋮ Generalized disk graphs ⋮ Reverse shortest path problem for unit-disk graphs ⋮ A combinatorial algorithm for the TDMA message scheduling problem ⋮ Dominating Cartesian products of cycles ⋮ Upper and lower bounds for deterministic broadcast in powerline communication networks ⋮ Roman domination in subgraphs of grids ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ On domination numbers of graphs bundles ⋮ Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs ⋮ Gridline indifference graphs ⋮ Impact of locality on location aware unit disk graphs ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Algebraic approach to fasciagraphs and rotagraphs ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ Unit disk graph recognition is NP-hard ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ A new bound on maximum independent set and minimum connected dominating set in unit disk graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs ⋮ The domination numbers of cylindrical grid graphs ⋮ Shortest hop multipath algorithm for wireless sensor networks ⋮ A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs ⋮ Compact and low delay routing labeling scheme for unit disk graphs ⋮ A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares ⋮ The impact of mobility on the geocasting problem in mobile ad-hoc networks: solvability and cost ⋮ Theory and application of width bounded geometric separators ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ The connected disk covering problem ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Conflict-free coloring of points on a line with respect to a set of intervals ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes

This page was built for publication: Unit disk graphs