Metraipolis › archive › dc_7162c5220b67
The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions — arXiv:2609.07253
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07253
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:07:15.716Z
- SHA-256 of the archived text
de2375d1615fcd29b39dac19884aaaf866c8d01b3fb549eda6adf710ffbf85d4- Stable URL of this page
https://metraipolis.com/documento/dc_7162c5220b67
How to cite
The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions — arXiv:2609.07253 — arXiv (en), https://arxiv.org/abs/2609.07253 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7162c5220b67 (Metraipolis archive dc_7162c5220b67, sha256 de2375d1615fcd29b39dac19884aaaf866c8d01b3fb549eda6adf710ffbf85d4)
BibTeX
@misc{dc7162c5220b67,
title = {The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions — arXiv:2609.07253},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07253},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7162c5220b67; sha256 de2375d1615fcd29b39dac19884aaaf866c8d01b3fb549eda6adf710ffbf85d4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07253. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are \emph{mutually visible} if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a \emph{Mutual Visibility Set} (\MVS) if every pair of vertices in $S$ is mutually visible. The concept of \MVS s in graphs has attracted significant attention since its introduction, as it provides an important structural property of graphs. However, determining a maximum \MVS\ in general graphs is computationally intractable; the decision problem of whether a graph admits an \MVS\ of size at least $k$ has been shown to be \emph{NP-complete}. Thus, prior work has focused on finding maximal \MVS s or restricting attention to specific graph classes. Cactus graphs form a fundamental low-treewidth class, yet the maximum \MVS\ problem for this class remains open. In this paper, we first determine the size of maximum \MVS~in cactus graphs, and introduce two self-stabilizing algorithms that construct such sets. The first algorithm uses a single BFS tree and stabilizes in $O(D)$ rounds with $O(\log n)$ bits per process on average; the second one uses parallel BFS trees and stabilizes in $O(|C_{\max}|+|T_{\max}|)$ rounds, which we show to be asymptotically tight as a function of these two parameters, even on graphs where $|C_{\max}|+|T_{\max}| = o(D)$.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.07253 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:02:21.575Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).