MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph is undirected (just like in Christofides algorithm). The point is, the problem I am working on requires me to find the MST with possibly lowest diameter (the number of nodes on the longest path between any two leaf nodes, equivalently, for the purpose of measuring the diameter one can treat all the edges of the MST as if they had the weight equal to 1).

I know that Boruvka’s, Prim’s and Kruskal’s algorithm can be used to find some MST, but can I influence them somehow to prefer the shortest (in the terms of the diameter) trees possible?

If the answer to the question above is negative, are there any algorithms or methods which either yield MST with some bounds on the tree diameter or, at least, are there any known methods of obtaining a bound on MST diameter for a given graph?

Diameter of a random graph

I’m considering the standard Erdös/Renyi $ G(n,p)$ model where we have $ n$ nodes and each possible edge is sampled independently with probability $ p = \frac{1}{n^\epsilon}$ .

It is relatively straightforward to show that, starting from any node $ u$ , the expected number of hops to reach every other node is $ 1/\epsilon$ . However, this does not say much about the probability of having a diameter of $ 1/\epsilon$ . (I could apply Markov’s inequality, but that gives a rather weak bound.)

Thus I’m looking for a reference to a concentration result that states that the diameter of such a random graph is $ O(1/\epsilon)$ with probability at least $ 1 – o(1)$ .

Bellman-Ford – is number of interations greater than diameter?


Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d.

Prove or disprove: in Bellman-Ford is the number of iterations always equal or lower than d.

I’m trying to solve this issue. What I tried was sketching a lot of graphs, however I have failed to find a single graph where the number of iterations would be higher than the diameter.

The only graph where the number of iterations wouldn’t be <= than diameter would be a graph with negative edges, however I found out that in undirected graph there can’t be any negative edges, otherwhere there would be a negative cycle.

So, AFAIK the statement is correct. However, how would I prove such a statement? I don’t even know how to start. Thanks for any help

Calculation of the diameter of a connected network in the CONGEST model

I need to show that in the CONGEST model, the diameter of a (connected) network can be calculated in $ O(m) $ rounds, with $ m $ indicating the number of edges of the network.

My idea would be the following: First a leader is determined by using the radius-growth algorithm which has a runtime of $ O (n) $ rounds. Because $ n \leq m – 1$ , that works.

After the leader was determined, the leader starts a BFS, which needs $ O(D)$ rounds (with $ D $ being the diameter of the network, which is at that point unknown, but of course $ D \leq m $ ). Then we can determine the node with the highest distance from the leader in $ O(D) $ rounds, let’s call this node $ a $ . Then we start another BFS from the node $ a $ and, again, determine the node with the highest distance from $ a $ , let’s call this node $ b $ . Then $ dist(a, b)$ should be the diameter $ D $ of the network.

The runtime seems to be okay, so it would be possible in $ O (m) $ rounds with this approach. The only problem I have is that I am not sure if this approach is correct, at least I am not able to prove it formally. I need to prove, if the $ dist(a, b) = D$ , then the two BFS find the nodes $ a $ and $ b$ . My idea would be that if the leader, which is determined by using the radius-growth algorithm, is either the node $ a $ or $ b $ , then trivially it would be correct. If it is neither $ a $ nor $ b $ (nor any other node at the ‘start’ or ‘end’ of a path with length $ D $ ), then during the first BFS we would at some point reach the path which represents the diameter. If without loss of generality the node $ b $ has a higher distance to the leader, then the leader would find $ b$ after the first BFS, because if it would find another node (let’s call this node $ x $ ), then $ dist(a, b) \neq D $ , because $ dist(a, x) $ would be the diameter and not $ dist(a, b)$ which would be a contradiction.

Is that right?

If a circle with a diameter of 12 contains a chord of length 6 sqrt2, what is the length of the minor arc intercepted by the chord?

I’ve been stuck on this question for a while now… the main problem is that I don’t know the way I should draw it.

Should I draw it so that the diameter is perpendicular to the chord (so it can bisect the chord & its arc), or should I create an inscribed angle with the chord and diameter?

I tried both ways and I still have no idea how to even get an answer. Any help is much appreciated!

Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $ G(V, E)$ , weight function $ w: E \rightarrow R, w(e) > 0\ \forall e \in E$ , find the spanning tree $ T(V, E’)$ of $ G$ such as maximal distance between vertices in $ T$ is minimal.

I’ve done my research and haven’t found much literature on this particular problem (I’ve seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there’s any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $ \Theta(n^3)$ solution exists here, but no full solution is anywhere.

I believe this community would benefit if solution is described here.

Diameter for permutations of bounded support

Let $ S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $ \sigma\in S$ moves $ O(1)$ elements of $ \{1,2,\dotsc,n\}$ . Let $ \Gamma$ be the graph whose set of vertices is the set of ordered pairs $ (i,j)$ , $ 1\leq i,j\leq n$ , $ i\ne j$ , and whose edges are $ ((i,j), (i,j)^\sigma)$ , $ \sigma\in S$ . (In other words, $ \Gamma$ is a Schreier graph.) Assume $ \Gamma$ is connected, i.e., $ S$ generates a $ 2$ -transitive group.

Must it be the case that $ \textrm{diam}(\Gamma) = O(n)$ ? Could it be the case that $ \textrm{diam}(\Gamma)\gg n^{1+\delta}$ , $ \delta>0$ , or even $ \delta=1$ ?

What are the answers to these questions if we assume that $ \langle S\rangle$ is all of $ \textrm{Alt}(n)$ or $ \textrm{Sym(n)}$ ?