John, thank you for the pointer, which I followed http://citeseer.ist.psu.edu/maggs94minimumcost.html and found some interesting things. In particuar, mesh connected computers and hyper-bus broadcast networks, where such algorithm is O(n) on a n x n mesh. So despite its seeming resource-thirstyness it's a good scalable algorithm. So once you have the mesh it's a blast.
----- Original Message ---- From: John Randall <[EMAIL PROTECTED]> To: Programming forum <[email protected]> Sent: Tuesday, June 27, 2006 12:14:10 PM Subject: Re: [Jprogramming] Minimal Spanning Tree on (min, max)-algebra transitive closure Oleg Kobchenko wrote: > Eesuk Chung published a very exciting algorithm in > the Minimal Spanning Tree essay, based on (min,max)-algebra (MMA), > in addition to Roger Hui's initial Kruskal algorithm > http://www.jsoftware.com/jwiki/Essays/Minimal_Spanning_Tree > > It's beautiful and the simplest MST algorithm I've seen. > Is there more cool stuff where it was coming from? > I wasn't able to find any discussion of MMA on the web about it. > or in textbooks, e.g. Introduction to Algorithms. > > This is a very nifty solution. See B. M. Maggs and S. A. Plotkin. Minimum-cost spanning tree as a path-finding problem. Information Processing Letters, 26(6):291--293, January 1988. for what is I think the original statement of this algorithm. It may have been folklore before this. Stating the problem in terms of max-min algebra comes from fuzzy logic, and is probably later. If a graph has V vertices and E edges, representing the problem as multiplications of the adjacency matrix makes it at least O(V^3). I believe Kruskal's algorithm is O(E log E), which is always faster. Prim's algorithm can be implemented to run even faster, especially for sparse graphs. That said, in no way undermines the utility and simplicity of this algorithm for small graphs. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
