论文标题
helly图和$ k $ -HELLY图中的距离问题
Distance problems within Helly graphs and $k$-Helly graphs
论文作者
论文摘要
图$ g $的球超图是所有可能中心的球家族和$ g $的半径。如果$ k $ wise的相交球的每个亚家族都有一个非空的共同交叉点，则它最多有$ k $。图形为$ k $ -HELLY（或HELLY，如果$ k = 2 $），如果其球超图最多具有$ k $。我们证明，可以计算W.H.P.的中央顶点和所有中位数。在$ \ tilde {\ cal o}（m \ sqrt {n}）$时间。这两个结果都扩展到更广泛的设置，在该设置中，我们在顶点集合上定义了非负成本函数。对于任何固定的$ k $，我们还提供了一个$ \ tilde {\ cal o}（m \ sqrt {kn}）$ - $ k $ - helly图中半径计算的时间随机算法。如果我们放松Helly数字的定义（对于文献中有时称为“几乎是Helly-Type”属性），那么我们的方法会导致一种近似算法，用于计算半径，并具有最多常数的添加单方面误差。
The ball hypergraph of a graph $G$ is the family of balls of all possible centers and radii in $G$. It has Helly number at most $k$ if every subfamily of $k$-wise intersecting balls has a nonempty common intersection. A graph is $k$-Helly (or Helly, if $k=2$) if its ball hypergraph has Helly number at most $k$. We prove that a central vertex and all the medians in an $n$-vertex $m$-edge Helly graph can be computed w.h.p. in $\tilde{\cal O}(m\sqrt{n})$ time. Both results extend to a broader setting where we define a non-negative cost function over the vertex-set. For any fixed $k$, we also present an $\tilde{\cal O}(m\sqrt{kn})$-time randomized algorithm for radius computation within $k$-Helly graphs. If we relax the definition of Helly number (for what is sometimes called an "almost Helly-type" property in the literature), then our approach leads to an approximation algorithm for computing the radius with an additive one-sided error of at most some constant.
