Distributed computation of temporal twins in periodic undirected time-varying graphs
<|reference_start|>Distributed computation of temporal twins in periodic undirected time-varying graphs: 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 $(\Delta,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 $\Delta$ and $d$ two integers, two distinct nodes $u$ and $v$ in $\mathcal G$ are $(\Delta,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 $\Delta$ consecutive instants. In particular when $d=0$, $u$ and $v$ can act during the $\Delta$ 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 $(\Delta,d)$-twins in $2p$ rounds, using messages of size $O(\delta_\mathcal G\log n)$, where $n$ is the total number of nodes and $\delta_\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.<|reference_end|>
@article{azerouk2024distributed,
    title={Distributed computation of temporal twins in periodic undirected
  time-varying graphs},
    author={Lina Azerouk (SU), Binh-Minh Bui-Xuan (NPA, SU, CNRS), Camille Palisoc
  (SU), Maria Potop-Butucaru (NPA, SU), Massinissa Tighilt (SU, NPA)},
    journal={arXiv preprint arXiv:2404.17195},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.17195},
    primaryClass={cs.DS}
}