论文标题
平衡图形图和一个顶点
Balancing graph Voronoi diagrams with one more vertex
论文作者
论文摘要
令$ g =（v，e）$为单位长度边缘和分配给其顶点的非负费用的图形。 Being given a list of pairwise different vertices $S=(s_1,s_2,\ldots,s_p)$, the {\em prioritized Voronoi diagram} of $G$ with respect to $S$ is the partition of $G$ in $p$ subsets $V_1,V_2,\ldots,V_p$ so that, for every $i$ with $1 \leq i \leq p $，一个顶点$ v $在$ v_i $中，并且仅当$ s_i $是$ s $中的最接近$ v $的顶点，并且在子集中$ \ {s_1，s_2，s_2，\ ldots中，$ s $ in $ s $中的$ v $ in $ s $ in $ s $中的$ v $。对于每$ i $，带有$ 1 \ leq i \ leq p $，顶点$ s_i $的{\ em load}等于$ v_i $中所有顶点的成本总和。 $ s $的负载等于$ s $的顶点的最大负载。我们研究了在$ S $结束时再增加一个顶点$ v $的问题，以最大程度地减少负载。此问题发生在考虑已经存在已经存在的设施的同时，以最佳定位新的服务设施（例如{\ it，例如{\ it，例如}，学校或医院），并目的是最大程度地减少站点上的最大拥塞。有一种用于在$ {\ cal o}（nm）$ n $ -vertex $ m $ m $ - 边缘图上解决此问题的蛮力算法。我们证明了$ m = n^{1+o（1）} $和$ p = 1 $的特殊情况的匹配时间下限，假设Abboud等人的所谓命中集猜想。在正面，我们在集团，路径和周期上介绍了此问题的简单线性时间算法，以及树木的几乎线性时间算法，正确的间隔图，并且（假设$ p $成为常数）有限的 - 树 - 树 - 树图。
Let $G=(V,E)$ be a graph with unit-length edges and nonnegative costs assigned to its vertices. Being given a list of pairwise different vertices $S=(s_1,s_2,\ldots,s_p)$, the {\em prioritized Voronoi diagram} of $G$ with respect to $S$ is the partition of $G$ in $p$ subsets $V_1,V_2,\ldots,V_p$ so that, for every $i$ with $1 \leq i \leq p$, a vertex $v$ is in $V_i$ if and only if $s_i$ is a closest vertex to $v$ in $S$ and there is no closest vertex to $v$ in $S$ within the subset $\{s_1,s_2,\ldots,s_{i-1}\}$. For every $i$ with $1 \leq i \leq p$, the {\em load} of vertex $s_i$ equals the sum of the costs of all vertices in $V_i$. The load of $S$ equals the maximum load of a vertex in $S$. We study the problem of adding one more vertex $v$ at the end of $S$ in order to minimize the load. This problem occurs in the context of optimally locating a new service facility ({\it e.g.}, a school or a hospital) while taking into account already existing facilities, and with the goal of minimizing the maximum congestion at a site. There is a brute-force algorithm for solving this problem in ${\cal O}(nm)$ time on $n$-vertex $m$-edge graphs. We prove a matching time lower bound for the special case where $m=n^{1+o(1)}$ and $p=1$, assuming the so called Hitting Set Conjecture of Abboud et al. On the positive side, we present simple linear-time algorithms for this problem on cliques, paths and cycles, and almost linear-time algorithms for trees, proper interval graphs and (assuming $p$ to be a constant) bounded-treewidth graphs.
