Results 1 to 10 of about 116,078 (220)
Strongly Hyperbolic Unit Disk Graphs [PDF]
, 2021 The class of Euclidean unit disk graphs is one of the most fundamental and well-studied graph classes with underlying geometry. In this paper, we identify this class as a special case in the broader class of hyperbolic unit disk graphs and introduce ...
Bläsius, Thomas +3 more
core +11 more sources
Liar's domination in unit disk graphs [PDF]
Theoretical Computer Science, 2020 In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\frac{11}{2}$-factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a ...
Ramesh K. Jallu +2 more
openaire +2 more sources
Unit Disk Visibility Graphs [PDF]
, 2021 We study unit disk visibility graphs, where the visibility relation between a pair of geometric entities is defined by not only obstacles, but also the distance between them. That is, two entities are not mutually visible if they are too far apart, regardless of having an obstacle between them.
Onur Çağırıcı, Deniz Ağaoğlu
openaire +3 more sources
Routing in Unit Disk Graphs [PDF]
Algorithmica, 2016 Let $S \subset \mathbb{R}^2$ be a set of $n$ sites. The unit disk graph $\text{UD}(S)$ on $S$ has vertex set $S$ and an edge between two distinct sites $s,t \in S$ if and only if $s$ and $t$ have Euclidean distance $|st| \leq 1$. A routing scheme $R$ for $\text{UD}(S)$ assigns to each site $s \in S$ a label $\ell(s)$ and a routing table $ (s)$.
Haim Kaplan +3 more
openaire +5 more sources
Improper colouring of (random) unit disk graphs [PDF]
Discrete Mathematics, 2005 For any graph $G$, the $k$-improper chromatic number $χ ^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to extend results of [McRe99,
Kang, Ross, J. +2 more
openaire +12 more sources
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs [PDF]
, 2018 A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since
Bonnet, E. +4 more
core +9 more sources
Sparse hop spanners for unit disk graphs
Computational Geometry, 2022 20 pages, 9 ...
Anirban Ghosh +3 more
openaire +6 more sources
Network Localization on Unit Disk Graphs [PDF]
2011 IEEE Global Telecommunications Conference - GLOBECOM 2011, 2011 5 ...
Nattakan Puttarak +2 more
openaire +3 more sources
Discrete Mathematics, 1990 AbstractUnit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set ...
Charles J. Colbourn +5 more
openaire +2 more sources
Balanced Line Separators of Unit Disk Graphs [PDF]
Computational Geometry, 2017 We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $\ell$ such that $\ell$ intersects at most $O(\sqrt{(m+n)\log{n}})$ disks and each of the halfplanes determined by $\ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the ...
Carmi, Paz +8 more
openaire +5 more sources