Distributed computation of temporal twins in periodic undirected time-varying graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909182964269056 |
|---|---|
| author | Azerouk, Lina Bui-Xuan, Binh-Minh Palisoc, Camille Potop-Butucaru, Maria Tighilt, Massinissa |
| author_facet | Azerouk, Lina Bui-Xuan, Binh-Minh Palisoc, Camille Potop-Butucaru, Maria Tighilt, Massinissa |
| contents | Twin nodes in a static network capture the idea of being substitutes for each other for maintaining paths of the same length anywhere in the network. In dynamic networks, we model twin nodes over a time-bounded interval, noted $(Δ,d)$-twins, as follows. A periodic undirected time-varying graph $\mathcal G=(G_t)_{t\in\mathbb N}$ of period $p$ is an infinite sequence of static graphs where $G_t=G_{t+p}$ for every $t\in\mathbb N$. For $Δ$ and $d$ two integers, two distinct nodes $u$ and $v$ in $\mathcal G$ are $(Δ,d)$-twins if, starting at some instant, the outside neighbourhoods of $u$ and $v$ has non-empty intersection and differ by at most $d$ elements for $Δ$ consecutive instants. In particular when $d=0$, $u$ and $v$ can act during the $Δ$ instants as substitutes for each other in order to maintain journeys of the same length in time-varying graph $\mathcal G$. We propose a distributed deterministic algorithm enabling each node to enumerate its $(Δ,d)$-twins in $2p$ rounds, using messages of size $O(δ_\mathcal G\log n)$, where $n$ is the total number of nodes and $δ_\mathcal G$ is the maximum degree of the graphs $G_t$'s. Moreover, using randomized techniques borrowed from distributed hash function sampling, we reduce the message size down to $O(\log n)$ w.h.p. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17195 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed computation of temporal twins in periodic undirected time-varying graphs Azerouk, Lina Bui-Xuan, Binh-Minh Palisoc, Camille Potop-Butucaru, Maria Tighilt, Massinissa Data Structures and Algorithms Twin nodes in a static network capture the idea of being substitutes for each other for maintaining paths of the same length anywhere in the network. In dynamic networks, we model twin nodes over a time-bounded interval, noted $(Δ,d)$-twins, as follows. A periodic undirected time-varying graph $\mathcal G=(G_t)_{t\in\mathbb N}$ of period $p$ is an infinite sequence of static graphs where $G_t=G_{t+p}$ for every $t\in\mathbb N$. For $Δ$ and $d$ two integers, two distinct nodes $u$ and $v$ in $\mathcal G$ are $(Δ,d)$-twins if, starting at some instant, the outside neighbourhoods of $u$ and $v$ has non-empty intersection and differ by at most $d$ elements for $Δ$ consecutive instants. In particular when $d=0$, $u$ and $v$ can act during the $Δ$ instants as substitutes for each other in order to maintain journeys of the same length in time-varying graph $\mathcal G$. We propose a distributed deterministic algorithm enabling each node to enumerate its $(Δ,d)$-twins in $2p$ rounds, using messages of size $O(δ_\mathcal G\log n)$, where $n$ is the total number of nodes and $δ_\mathcal G$ is the maximum degree of the graphs $G_t$'s. Moreover, using randomized techniques borrowed from distributed hash function sampling, we reduce the message size down to $O(\log n)$ w.h.p. |
| title | Distributed computation of temporal twins in periodic undirected time-varying graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17195 |