Results 41 to 50 of about 142,780 (319)

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

Latency-optimal virtual backbone construction with acoustic communication in underwater sensor networks

International Journal of Distributed Sensor Networks, 2017
The high attenuation of radio signals in water leaves acoustic waves the most viable communication media for underwater sensor networks. Nevertheless, acoustic communication suffers from significantly high latency because of its low propagation speed ...
Xin Bai, Xiaohui Wei, Sen Bai
doaj   +1 more source

Spanners for geometric intersection graphs with applications

Journal of Computational Geometry, 2012
A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real numbert>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of verticesu,v in G, there exists a path in G' of length at most t ...
Martin Fürer, Shiva Prasad Kasiviswanathan   +1 more
doaj   +1 more source

Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms [PDF]

Physical Review A
Recent progress in quantum computing and quantum simulation of many-body systems with arrays of neutral atoms using Rydberg excitation has provided unforeseen opportunities towards computational advantage in solving various optimization problems.
Ahmed M. Farouk, I. Beterov, Peng Xu, I. Ryabtsev   +3 more
semanticscholar   +1 more source

Sparse Hop Spanners for Unit Disk Graphs [PDF]

International Symposium on Algorithms and Computation, 2020
A unit disk graph $G$ on a given set of points $P$ in the plane is a geometric graph where an edge exists between two points $p,q \in P$ if and only if $|pq| \leq 1$.
A. Dumitrescu, Anirban Ghosh, Csaba D. T'oth   +2 more
semanticscholar   +1 more source

Hierarchically specified unit disk graphs

Theoretical Computer Science, 1997
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Marathe, Madhav V., Radhakrishnan, Venkatesh, Hunt, Harry B., Ravi, S.S.   +3 more
openaire   +1 more source

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.
Marathe, M. V., Breu, H., Hunt, H. B. III, Ravi, S. S., Rosenkrantz, D. J.   +4 more
openaire   +1 more source

Planar subgraphs without low-degree nodes [PDF]

, 2011
We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k.
A. Liebers, C.D. Tóth, E. Kranakis, G.T. Toussaint, I. Rutter, K.R. Gabriel, L. Barrière, M. Abellanas, M. Al-Jubeh, M.R. Garey   +9 more
core   +2 more sources

Network Localization on Unit Disk Graphs [PDF]

2011 IEEE Global Telecommunications Conference - GLOBECOM 2011, 2011
5 ...
Kaewprapha, Phisan, Li, Jing, Puttarak, Nattakan   +2 more
openaire   +2 more sources

Dominating Set Algorithms for Wireless Sensor Networks Survivability

IEEE Access, 2018
Limited energy of the sensors is one of the key issues towards realizing a reliable wireless sensor network (WSN), which can survive under the emerging WSN applications.
Tayler Pino, Salimur Choudhury, Fadi Al-Turjman   +2 more
doaj   +1 more source