4

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

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
Rambo
  • 741
  • 1
  • 8
  • 12

1 Answers1

6

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 - µ)).

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • 1
    What is meant by "compute the interval [a, b] of µ that induces the same argmax partition." ? – galath Mar 12 '17 at 10:18
  • 2
    @galath If the distance to vertices from the middle of an edge has argmaxes at µ = 0, 0.2, 0.5, 0.7, 0.9, 1 depending, then the [a, b] interval for partitioning [0, 0.2, 0.5] [0.7, 0.9, 1] is the interval [0.5, 0.7]. – David Eisenstat Mar 12 '17 at 13:28
  • Another way to think of the last part is that the distance from a vertex w to a point µ along between u and v looks like a "mountain" when plotted against µ, with each side rising at 45 degrees to a peak at the argmax. If we plot, at each µ value, the maximum of all these mountains (over all vertices w), we get a "mountain range". The goal then is to look for the lowest point in this mountain range that occurs in [0, len(u--v)], which must occur either at one of the endpoints, or at a "valley". ... – j_random_hacker Mar 21 '19 at 14:38
  • ... If we add each mountain to the range in increasing argmax order, adding a mountain always erases 0 or more of the rightmost existing mountains and valleys, and then adds 0 or 1 new valley, and 1 mountain, to the right. Since each mountain and valley is added once and deleted at most once, and both (a) testing whether a new mountain hides another mountain and (b) finding their valley if not are O(1)-time, this takes linear time. At the end, the surviving valleys can be scanned and the lowest in [0, len(u--v)] chosen. This needs to be repeated for each edge uv, and the lowest overall kept. – j_random_hacker Mar 21 '19 at 14:42