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 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 ⋮ Wireless networking, dominating and packing ⋮ The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Routing of single-source and multiple-source queries in static sensor networks ⋮ Unit disk graphs ⋮ Note on coloring of double disk graphs ⋮ Approximation algorithms for intersection graphs ⋮ Minimum clique partition in unit disk graphs ⋮ Independent dominating set problem revisited ⋮ On the chromatic number of random geometric graphs ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ Clustering the wireless ad hoc networks: a distributed learning automata approach ⋮ An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks ⋮ Coloring the complements of intersection graphs of geometric figures ⋮ Routing in unit disk graphs ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ On the parameterized complexity of the edge monitoring problem ⋮ On the complexity of bandwidth allocation in radio networks ⋮ Mixed-integer programming models for tower crane selection and positioning with respect to mutual interference ⋮ The critical node detection problem in networks: a survey ⋮ Scaling laws for maximum coloring of random geometric graphs ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Connected dominating sets on dynamic geometric graphs ⋮ On connected domination in unit ball graphs ⋮ An exact algorithm for minimum CDS with shortest path constraint in wireless networks ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ On distance constrained labeling of disk graphs ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ The complexity of data aggregation in static and dynamic wireless sensor networks ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model ⋮ Dominating set of rectangles intersecting a straight line ⋮ Cliques in hyperbolic random graphs ⋮ Stabbing pairwise intersecting disks by five points ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ Roman \(\{k\}\)-domination in trees and complexity results for some classes of graphs ⋮ In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ Efficient algorithms for network localization using cores of underlying graphs ⋮ Maximum scan statistics and channel assignment problems in homogeneous wireless networks ⋮ Hierarchically specified unit disk graphs ⋮ Conflict-free coloring of unit disks ⋮ Path optimization for graph partitioning problems ⋮ Balanced cut approximation in random geometric graphs ⋮ A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph ⋮ An order-based algorithm for minimum dominating set with application in graph mining ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ Domination number of the cross product of paths ⋮ Revising Johnson's table for the 21st century ⋮ Twin-width and polynomial kernels ⋮ Graph imperfection. I ⋮ The on-line first-fit algorithm for radio frequency assignment problems. ⋮ On-line coloring of geometric intersection graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ A tight analysis of geometric local search ⋮ The chromatic and clique numbers of random scaled sector graphs
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
