Unit disk graph recognition is NP-hard
From MaRDI portal
Publication:1384186
DOI10.1016/S0925-7721(97)00014-XzbMath0894.68099WikidataQ29028109 ScholiaQ29028109MaRDI QIDQ1384186
Heinz Breu, David G. Kirkpatrick
Publication date: 13 April 1998
Published in: Computational Geometry (Search for Journal in Brave)
Related Items
On the minimum and maximum selective graph coloring problems in some graph classes ⋮ Sparse hop spanners for unit disk graphs ⋮ On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ FO model checking on geometric graphs ⋮ On some applications of the selective graph coloring problem ⋮ Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Intersection graphs of homothetic polygons ⋮ Unit disk representations of embedded trees, outerplanar and multi-legged graphs ⋮ Arrangements of orthogonal circles with many intersections ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Structural parameterizations with modulator oblivion ⋮ On the reconstruction of three-dimensional protein structures from contact maps ⋮ Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs ⋮ Unit ball graphs on geodesic spaces ⋮ Complexity of edge monitoring on some graph classes ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Sphere and dot product representations of graphs ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Faster algorithms for cycle hitting problems on disk graphs ⋮ Random geometric graph: some recent developments and perspectives ⋮ Low Ply Drawings of Trees ⋮ Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm ⋮ Distinguishing graphs via cycles ⋮ Dilation coefficient, plane-width, and resolution coefficient of graphs ⋮ Computing stable Demers cartograms ⋮ On arrangements of orthogonal circles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes ⋮ Shifting strategy for geometric graphs without geometry ⋮ The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ On Vertex- and Empty-Ply Proximity Drawings ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Minimum clique partition in unit disk graphs ⋮ Theoretical Aspects of Graph Models for MANETs ⋮ Implicit representation conjecture for semi-algebraic graphs ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ Identifying and Locating–Dominating Codes in (Random) Geometric Networks ⋮ Surrounding Nodes in Coordinate-Free Networks ⋮ A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Location-oblivious distributed unit disk graph coloring ⋮ On connected domination in unit ball graphs ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ On distance constrained labeling of disk graphs ⋮ Arrangements of orthogonal circles with many intersections ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ Sphericity, cubicity, and edge clique covers of graphs ⋮ Unnamed Item ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ The Number of Bits Needed to Represent a Unit Disk Graph ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ The number of disk graphs ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Deployment optimization of multi-hop wireless networks based on substitution graph ⋮ Global Rigidity of Unit Ball Graphs ⋮ Unnamed Item ⋮ Balanced line separators of unit disk graphs ⋮ Unnamed Item ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ \( L ( 2 , 1 )\)-labeling of disk intersection graphs ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation ⋮ Weak Unit Disk and Interval Representation of Graphs ⋮ Testing for high-dimensional geometry in random graphs ⋮ Unnamed Item ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ Bisectored unit disk graphs ⋮ Strong chromatic index of \(K_{1, t}\)-free graphs ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ Monotone maps, sphericity and bounded second eigenvalue ⋮ On-line coloring of geometric intersection graphs
Cites Work
- On the sphericity and cubicity of graphs
- Unit disk graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Coin graphs, polyhedra, and conformal mapping
- Incidence matrices and interval graphs
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
