最小直径生成树算法

Question

给定一个无向和连通图G，找到直径最小的生成树。

Answer 1

singhsumit将相关论文链接到Hassin and Tamir，标题为“关于最小直径生成树问题”，但他的答案目前已被删除。本文的主要思想是在无向图中找到最小直径生成树可以通过找到图的“绝对1中心”并返回根植于其中的最短路径树来实现。

绝对1中心是指顶点或边缘上的点，从该点到最远顶点的距离最小。这可以通过Kariv和Hakimi（网络定位问题的一种算法方法，I：p-中心）算法或早期的Hakimi，Schmeichel和Pierce算法（网络中的p-中心）找到，我将试图从运行时间和几十年的事后重建。 （愚蠢的薪水墙。）

使用Floyd-Warshall或Johnson的算法计算所有对距离。对于每个边u-v，按如下方式在该边上找到1中心的最佳候选。

设边u-v上的点由从0（u本身）到len（u-v）（v本身）范围内的μ索引。从指数μ处的点到顶点w的距离为

min（μ+ d（u，w），len（u-v）-μ+ d（v，w））。

作为μ的函数，这个量在

增加后减少，在最大

μ=（LEN（U - V）+ d（V，W） - d（ u，w））/ 2。

按此argmax对顶点排序。对于数组中的每个分区，将其分为左侧子数组和右侧子数组，计算引起相同argmax分区的μ的时间间隔[a，b]。将此区间与[0，len（u - v）]相交;如果十字路口是空的，然后继续前进。否则，从由u索引的点开始的左子阵列中找出最大距离L，并从由u索引的点开始的右子阵列中的最大距离R索引b。 （计算这些最大值的成本可以分摊到每个分区的O（1），通过从左到右和从右到左的扫描开始。）最佳选择是[a，b]中的μ使最大值（L - （μ - ​​a），R +（b - μ））最小化。