Results 1 to 10 of about 83,874 (238)
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
On Forbidden Induced Subgraphs for Unit Disk Graphs [PDF]
Discrete & Computational Geometry, 2018 A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit
Atminas, Aistis, Zamaraev, Viktor
core +5 more sources
Parameterized Study of Steiner Tree on Unit Disk Graphs [PDF]
Algorithmica, 2020 We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R? V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at ...
Bhore, Sujoy +3 more
core +6 more sources
Dynamic Parameterized Problems on Unit Disk Graphs [PDF]
In this paper, we study fundamental parameterized problems such as k-Path/Cycle, Vertex Cover, Triangle Hitting Set, Feedback Vertex Set, and Cycle Packing for dynamic unit disk graphs.
An, Shinwoo +8 more
core +5 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