Unit disk graph recognition is NP-hard
From MaRDI portal
Publication:1384186
DOI10.1016/S0925-7721(97)00014-XzbMATH Open0894.68099WikidataQ29028109 ScholiaQ29028109MaRDI QIDQ1384186FDOQ1384186
Authors: Heinz Breu, David Kirkpatrick 
Publication date: 13 April 1998
Published in: Computational Geometry (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Unit disk graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- Title not available (Why is that?)
- Coin graphs, polyhedra, and conformal mapping
- On the sphericity and cubicity of graphs
Cited In (90)
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- Faster algorithms for cycle hitting problems on disk graphs
- Proper colorability of segment intersection graphs
- Complexity of recognizing multidistance graphs in \(\mathbb{R}^d\)
- Random geometric graph: some recent developments and perspectives
- Bisectored unit disk graphs
- Surrounding nodes in coordinate-free networks
- On the complexity of target set selection in simple geometric networks
- Establishing herd immunity is hard even in simple geometric networks
- QPTAS and subexponential algorithm for maximum clique on disk graphs
- Balanced line separators of unit disk graphs
- Reconstruction of random geometric graphs: breaking the \(\varOmega (r)\) distortion barrier
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- Title not available (Why is that?)
- Low Ply Drawings of Trees
- Unit ball graphs on geodesic spaces
- Structural parameterizations with modulator oblivion
- Structural parameterizations with modulator oblivion
- Deployment optimization of multi-hop wireless networks based on substitution graph
- On vertex- and empty-ply proximity drawings
- \( L ( 2 , 1 )\)-labeling of disk intersection graphs
- Complexity of edge monitoring on some graph classes
- On reverse shortest paths in geometric proximity graphs
- Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs
- Arrangements of orthogonal circles with many intersections
- Linear-time approximation algorithms for unit disk graphs
- A survey on variant domination problems in geometric intersection graphs
- Adjacency graphs of polyhedral surfaces
- Computing stable Demers cartograms
- Sparse hop spanners for unit disk graphs
- Finding geometric representations of apex graphs is NP-hard
- Location-oblivious distributed unit disk graph coloring
- On the minimum and maximum selective graph coloring problems in some graph classes
- On Embeddability of Unit Disk Graphs onto Straight Lines
- Identifying and locating-dominating codes in (random) geometric networks
- Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
- An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
- Implicit representation conjecture for semi-algebraic graphs
- Sublinear approximation algorithms for boxicity and related problems
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Intersection graphs of homothetic polygons
- Theoretical Aspects of Graph Models for MANETs
- Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Distinguishing graphs via cycles
- FO model checking on geometric graphs
- On embeddability of unit disk graphs onto straight lines
- On forbidden induced subgraphs for unit disk graphs
- FO model checking of geometric graphs
- On connected domination in unit ball graphs
- The number of bits needed to represent a unit disk graph
- Shifting strategy for geometric graphs without geometry
- On-line coloring of geometric intersection graphs
- Testing for high-dimensional geometry in random graphs
- Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Arrangements of orthogonal circles with many intersections
- Unit disk representations of embedded trees, outerplanar and multi-legged graphs
- Minimum bisection is NP-hard on unit disk graphs
- On the reconstruction of three-dimensional protein structures from contact maps
- Sphere and dot product representations of graphs
- Title not available (Why is that?)
- PTAS for the minimum weighted dominating set in growth bounded graphs
- Minimum bisection is NP-hard on unit disk graphs
- Sphericity, cubicity, and edge clique covers of graphs
- On some applications of the selective graph coloring problem
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- Minimum clique partition in unit disk graphs
- On distance constrained labeling of disk graphs
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Strong chromatic index of \(K_{1, t}\)-free graphs
- Perfectness and imperfectness of unit disk graphs on triangular lattice points
- Approximating minimum independent dominating sets in wireless networks
- The number of disk graphs
- Co-bipartite neighborhood edge elimination orderings
- On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
- A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
- Dilation coefficient, plane-width, and resolution coefficient of graphs
- On the recognition of unit disk graphs and the distance geometry problem with ranges
- The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems
- Recognizing tough graphs is NP-hard
- Global Rigidity of Unit Ball Graphs
- A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
- Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm
- Hexagonal unit network - a tool for proving the NP-completeness results of geometric problems
- Refining the hierarchies of classes of geometric intersection graphs
- Monotone maps, sphericity and bounded second eigenvalue
- On arrangements of orthogonal circles
- Weak unit disk and interval representation of graphs
- Title not available (Why is that?)
This page was built for publication: Unit disk graph recognition is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384186)
