论文标题
最大外平图中的2中心问题
The 2-center Problem in Maximal Outerplanar Graph
论文作者
论文摘要
我们考虑在最大外平面图中计算2中心的问题。在这个问题中，我们希望找到一个最佳解决方案，其中两个中心覆盖了最小半径的所有顶点。我们提供以下结果。我们可以在给定的最大外平面图中计算$ O（n^2）$的最佳半径，并使用$ n $顶点。我们尝试让最大外平面图切成两个具有内部边缘的子图，每个中心将覆盖连续的顶点。
We consider the problem of computing 2-center in maximal outerplanar graph. In this problem, we want to find an optimal solution where two centers cover all the vertices with the smallest radius. We provide the following result. We can compute the optimal centers and the optimal radius in $O(n^2)$ time for a given maximal outerplanar graph with $n$ vertices. We try to let the maximal outerplanar graph be cut into two subgraphs with an internal edge, each center will cover vertices which are continuous.
