minimum diameter of spanning tree

minimum diameter of spanning tree

Post by Dick » Sun, 06 Dec 1998 04:00:00



The diameter of a tree is the maximum distance between any two vertices.
Given a connected, undirected graph, please find a spanning tree of
minimum diameter. Prove that your result is correct, too.

does the above have any relationship with minimum spanning tree.

Dick Guan

 
 
 

minimum diameter of spanning tree

Post by Maynard Handl » Sun, 06 Dec 1998 04:00:00




> The diameter of a tree is the maximum distance between any two vertices.
> Given a connected, undirected graph, please find a spanning tree of
> minimum diameter. Prove that your result is correct, too.

> does the above have any relationship with minimum spanning tree.

>* Guan

Wow, are we supposed to be such idiots we cannot spot an obvious course
question?
Get off off you fat ass, go to the library, and try to think.

Maynard

--
My opinion only

 
 
 

minimum diameter of spanning tree

Post by David Sows » Sun, 06 Dec 1998 04:00:00


Quote:> Wow, are we supposed to be such idiots we cannot spot an obvious course
> question?

Heh, actually we should protest that professors ask inane course
work questions in the first place. A lot of coursework is
high falutin' and contrived.

Quote:> Get off off you fat ass, go to the library, and try to think.

If one moron has done it, it will be repeated in coursework
for centuries to follow.
Quote:> My opinion only

Yup.

Best Regards,
                David Sowsy

// "It was a time when second rate men did first rate work."
// --Dirac on Quantum Physics in 1925-26
// http://www.cs.uml.edu/~dsowsy

 
 
 

1. minimum spanning tree problem

That's probably not provable without more restrictions,
since an order N*log(N) algorithm exists at least for the
case of a graph embedded in a Cartesian coordinate space
with the usual Euclidean metric. I think the sketch of a
proof I saw recently was either in the local library's copy
of _Computational Complexity_ by Christos Papadimitriou
(Addison-Wesley 1994, ISBN 0-201-53082-1), or else in its
copy of _Computational Geometry: An Introduction_ (Texts and
Monographs in Computer Science) by Franco P. Preparata,
Michael Ian Shamos, (Springer-Verlag 1987, ISBN
0-387-96131-3); I consult both fairly often.

One other way to get to the result is to build on Fortune's
N*log(N) algorithm for a Delauney triangulation of the
graph, which limits the edges that must be investigated for
inclusion in the minimal spanning tree at each node to at
most 6; now use a greedy algorithm from that start to
construct the minimal spanning tree.

I'd _love_ to find an online implementation of an N*log(N)
Symmetric Euclidean MST, in Java or anything spelled closely
enough to Java to port, since my own use of the MST is at
least O(N^2) in construction, and quite probably worse,
making it really tedious for graphs of several thousand
vertices, and it is tough to implement from a book you
cannot carry to your workspace, but so far, several requests
have found no offers, so I suppose some less lazy day I must
do the work myself.

xanthian.

2. Info. on Magazines

3. minimum spanning tree for a DIRECTED graph

4. I will trade 3D Studio for Lightwave.

5. Find a minimum directed spanning tree.

6. scanning calculator?

7. Minimum Spanning Trees

8. RenderMan course at SIGGRAPH 2000

9. need help in finding minimum spanning path

10. Finding minimum angle span

11. Minimal spanning tree with moving points?

12. Minimal Cost Spanning Tree

13. BSP-Tree construction with minimum splits