Telephone problems with failures
Telephone problems with failures
复制标题
电话故障的问题
DOI：
10.1137/0607002
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
M. Hawrylycz
中科院分区：
文献类型：
--
作者：
K. Berman;M. Hawrylycz
考虑一个有n个顶点的多图G，其边是线性有序的。G的顶点可以代表人，边可以代表人对之间的双向交流。如果存在从$\upsilon $到w的升序边路径，即使删除了G的任意k条边，顶点$\upsilon $在与顶点w通信时也是k-故障安全的。在本文中，我们证明了G的最小尺寸$\mu ( n,k )$，使得一个顶点与其他每个顶点通信k-failure-safe为$\mu ( n,k ) = \lceil ( ( k + 2 )/2 ) ( n - 1 ) \rceil $对于$k\leqq n - 2$和$\mu ( n,k ) = \lceil ( ( k + 1 )/2 )n \rceil $对于$k\geqq n - 2$。我们还证明了对于$k\geqq 1$， G的最小尺寸$\tau ( n,k )$使得每个顶点与其他每个顶点通信k-failure-safe满足$\mu ( n,k ) + n - 2 \lceil \sqrt{n} \rceil \leqq \tau ( n,k )\leqq \lfloor ( k + 3/ 2 ) ( n - 1 ) \rfloor $。为$k = 0$找到$\tau ( n,k )$的问题是众所周知的电话问题。
Consider a multigraph G on n vertices whose edges are linearly ordered. The vertices of G may represent people and the edges two-way communication between pairs of people. A vertex $\upsilon $ is k-failure-safe in communicating with a vertex w if there is a path of ascending edges from $\upsilon $ to w even when any k edges of G are deleted. In this paper, we show that the minimum size $\mu ( n,k )$ of G such that one vertex communicates k-failure-safe with every other vertex is given by $\mu ( n,k ) = \lceil ( ( k + 2 )/2 ) ( n - 1 ) \rceil $ for $k\leqq n - 2$ and $\mu ( n,k ) = \lceil ( ( k + 1 )/2 )n \rceil $ for $k\geqq n - 2$. We also show that for $k\geqq 1$ the minimum size $\tau ( n,k )$ of G such that every vertex communicates k-failure-safe with every other vertex satisfies $\mu ( n,k ) + n - 2 \lceil \sqrt{n} \rceil \leqq \tau ( n,k )\leqq \lfloor ( k + 3/ 2 ) ( n - 1 ) \rfloor $. The problem of finding $\tau ( n,k )$ for $k = 0$ is the well-known telephone problem.