Results 21 to 30 of about 83,874 (238)
Simple heuristics for unit disk graphs [PDF]
Networks, 1995 AbstractUnit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set.
S. S. Ravi +4 more
openaire +2 more sources
Minimum Bisection Is NP-hard on Unit Disk Graphs [PDF]
Information and Computation, 2014 17 pages, 6 ...
Díaz Cort, Josep, Mertzios, George B.
openaire +8 more sources
compact routing in unit disk graphs
, 2020 Let V ⊂ ℝ² be a set of n sites in the plane. The unit disk graph DG(V) of V is the graph with vertex set V where two sites v and w are adjacent if and only if their Euclidean distance is at most 1. We develop a compact routing scheme ℛ for DG(V). The routing scheme ℛ preprocesses DG(V) by assigning a label 𝓁(v) to every site v in V.
Mulzer, Wolfgang, Willert, Max
openaire +4 more sources
Hierarchically specified unit disk graphs
Theoretical Computer Science, 1997 AbstractWe characterize the complexity of a number of basic optimization problems for unit disk graphs specified hierarchically as in [2, 17, 19, 20]. Both PSPACE-hardness results and polynomial time approximations are presented for most of the problems considered.
Venkatesh Radhakrishnan +3 more
openaire +2 more sources
Reverse Shortest Path Problem for Unit-Disk Graphs [PDF]
, 2021 Given a set P of n points in the plane, the unit-disk graph Gr(P) with respect to a parameter r is an undirected graph whose vertex set is P such that an edge connects two points p, q \in P if the Euclidean distance between p and q is at most r (the weight of the edge is 1 in the unweighted case and is the distance between p and q in the weighted case).
Wang, Haitao, Zhao, Yiming
openaire +4 more sources
Approximating Minimum Independent Dominating Sets in Wireless Networks [PDF]
, 2007 We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth.
Hurink, J.L., Nieberg, T.
core +6 more sources
Approximation Algorithms for Unit Disk Graphs [PDF]
, 2005 We consider several graph theoretic problems on unit disk graphs (Maximum Independent Set, Minimum Vertex Cover, and Minimum (Connected) Dominating Set) relevant to mobile ad hoc networks. We propose two new notions: thickness and density. If the thickness of a unit disk graph is bounded, then the mentioned problems can be solved in polynomial time ...
openaire +3 more sources
Efficient independent set approximation in unit disk graphs [PDF]
Discrete Applied Mathematics, 2020 Abstract We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a 2.16-approximation algorithm that runs in O ( n log 2 n ) time and a 2 ...
Gautam K. Das +2 more
openaire +3 more sources
Bidimensionality and Geometric Graphs
, 2011 In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on classes of graphs which are not minor closed, but instead exhibit a ...
Fomin, Fedor V. +2 more
core +2 more sources
On Geometric Spanners of Euclidean and Unit Disk Graphs [PDF]
, 2008 We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{del\approx 2.42$; however, its degree may not be bounded.
Perkovic, Ljubomir, Kanj, Iyad A.
openaire +5 more sources