Fault-Equivalent Lowest Common Ancestors
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916493902479360 |
|---|---|
| author | Petruschka, Asaf |
| author_facet | Petruschka, Asaf |
| contents | Let $T$ be a rooted tree in which a set $M$ of vertices are marked. The lowest common ancestor (LCA) of $M$ is the unique vertex $\ell$ with the following property: after failing (i.e., deleting) any single vertex $x$ from $T$, the root remains connected to $\ell$ if and only if it remains connected to some marked vertex. In this note, we introduce a generalized notion called $f$-fault-equivalent LCAs ($f$-FLCA), obtained by adapting the above view to $f$ failures for arbitrary $f \geq 1$. We show that there is a unique vertex set $M^* = \operatorname{FLCA}(M,f)$ of minimal size such after the failure of any $f$ vertices (or less), the root remains connected to some $v \in M$ iff it remains connected to some $u \in M^*$. Computing $M^*$ takes linear time. A bound of $|M^*| \leq 2^{f-1}$ always holds, regardless of $|M|$, and holds with equality for some choice of $T$ and $M$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11049 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fault-Equivalent Lowest Common Ancestors Petruschka, Asaf Data Structures and Algorithms Let $T$ be a rooted tree in which a set $M$ of vertices are marked. The lowest common ancestor (LCA) of $M$ is the unique vertex $\ell$ with the following property: after failing (i.e., deleting) any single vertex $x$ from $T$, the root remains connected to $\ell$ if and only if it remains connected to some marked vertex. In this note, we introduce a generalized notion called $f$-fault-equivalent LCAs ($f$-FLCA), obtained by adapting the above view to $f$ failures for arbitrary $f \geq 1$. We show that there is a unique vertex set $M^* = \operatorname{FLCA}(M,f)$ of minimal size such after the failure of any $f$ vertices (or less), the root remains connected to some $v \in M$ iff it remains connected to some $u \in M^*$. Computing $M^*$ takes linear time. A bound of $|M^*| \leq 2^{f-1}$ always holds, regardless of $|M|$, and holds with equality for some choice of $T$ and $M$. |
| title | Fault-Equivalent Lowest Common Ancestors |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.11049 |