Results 1 to 10 of about 124,454 (161)
Improper colouring of (random) unit disk graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 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$.
Ross J. Kang +2 more
doaj +9 more sources
Discrete Mathematics, 1990 Any given \(n\) points in the plane form the vertices of some graph by the convention that distinct points are adjacent whenever their distance is at most 2. The resulting graph is called a unit disk graph, since it is the intersection graph of the unit disks around the given \(n\) points.
Clark, Brent N. +2 more
openaire +3 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.
��a����r��c��, Onur +1 more
openaire +3 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 +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 +3 more sources
Location Oblivious Distributed Unit Disk Graph Coloring [PDF]
Algorithmica, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Barbeau, Michel +4 more
openaire +1 more source
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 +6 more sources
Sparse hop spanners for unit disk graphs
Computational Geometry, 2022 20 pages, 9 ...
Adrian Dumitrescu +2 more
openaire +5 more sources
Metric Dimension for Gabriel Unit Disk Graphs is NP-Complete [PDF]
, 2013 We show that finding a minimal number of landmark nodes for a unique virtual addressing by hop-distances in wireless ad-hoc sensor networks is NP-complete even if the networks are unit disk graphs that contain only Gabriel edges.
J. Díaz, P. Bose, R. Tamassia
core +1 more source
Minimum Clique Partition in Unit Disk Graphs [PDF]
Graphs and Combinatorics, 2011 Comment: 12 pages, 3 ...
Dumitrescu, Adrian, Pach, János
openaire +3 more sources