最小直径生成树算法 [英] Algorithm for minimum diameter spanning tree

问题描述

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

解决方案

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的距离为：b
$ b

（μ+ d（u，w），len（u-作为μ的一个函数，这个数量是增加的，然后是减少的，其中最大值为

<μ>μ=（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 - μ））。

Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.

解决方案

singhsumit linked the relevant paper by Hassin and Tamir, entitled "On the minimum diameter spanning tree problem", but his answer is currently deleted. The main idea from the paper is that finding a minimum diameter spanning tree in an undirected graph can be accomplished by finding the "absolute 1-center" of the graph and returning a shortest path tree rooted there.

The absolute 1-center is the point, either on a vertex or an edge, from which the distance to the furthest vertex is minimum. This can be found via an algorithm of Kariv and Hakimi (An Algorithmic Approach to Network Location Problems. I: the p-Centers) or an earlier algorithm of Hakimi, Schmeichel, and Pierce (On p-Centers in Networks), which I will attempt to reconstruct from just the running time and decades of hindsight. (Stupid pay walls.)

Use Floyd--Warshall or Johnson's algorithm to compute all-pairs distances. For each edge u--v, find the best candidate for a 1-center on that edge as follows.

Let the points on the edge u--v be indexed by µ ranging from 0 (u itself) to len(u--v) (v itself). The distance from the point at index µ to a vertex w is

min(µ + d(u, w), len(u--v) - µ + d(v, w)).

As a function of µ, this quantity is increasing and then decreasing, with the maximum at

µ = (len(u--v) + d(v, w) - d(u, w))/2.

Sort the vertices by this argmax. For each partition of the array into a left subarray and a right subarray, compute the interval [a, b] of µ that induce the same argmax partition. Intersect this interval to [0, len(u--v)]; if the intersection is empty, then move on. Otherwise, find the maximum distance L in the left subarray from the point on u--v indexed by a, and the maximum distance R in the right subarray from the point on u--v indexed by b. (The cost of computing these maximums can be amortized to O(1) for each partition, by scanning left-to-right and right-to-left at the beginning.) The best choice is the µ in [a, b] that minimizes max(L - (µ - a), R + (b - µ)).

这篇关于最小直径生成树算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！