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
