From: "Eckhard Hennig" Subject: Re: HELP: Kruskal algorithm extension Date: Thu, 11 Mar 1999 16:23:41 +0100 Newsgroups: sci.op-research,sci.math.symbolic,sci.math.num-analysis Keywords: Finding the k largest trees in a graph Jesus Cerquides wrote in message <36E7BE48.BC824769@ubs.com>... > >Everybody knows about Kruskal algorithm for finding the maximum spanning >tree in a labeled graph. >I need to know whether there is any algorithm for finding k different >spanning trees with the >k higher values. > >Any help or references would be appreciated. If I understand you correctly then what you are looking for is a algorithm that finds the k largest trees in a labeled graph with weighted edges. You will find such an algorithm in this paper by Gabow: Gabow, H. N., "Two Algorithms for Generating Weighted Spanning Trees in Order", SIAM Journal of Computing, vol. 6, no. 1, March 1977, pp. 139–150 HTH, Eckhard ----------------------------------------------------------- Dipl.-Ing. Eckhard Hennig mailto:hennig@itwm.uni-kl.de Institut fuer Techno- und Wirtschaftsmathematik e.V. (ITWM) Erwin-Schroedinger-Strasse, 67663 Kaiserslautern, Germany Voice: +49-(0)631-205-3126 Fax: +49-(0)631-205-4139 http://www.itwm.uni-kl.de/as/employees/hennig.html ITWM - Makers of Analog Insydes for Mathematica http://www.itwm.uni-kl.de/as/products/ai ----------------------------------------------------------- ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: HELP: Kruskal algorithm extension Date: 11 Mar 1999 09:13:11 -0800 Newsgroups: sci.op-research,sci.math.symbolic,sci.math.num-analysis In <7c8na2$o6c$1@sun.rhrk.uni-kl.de> "Eckhard Hennig" writes: > If I understand you correctly then what you are looking for is a algorithm > that finds the k largest trees in a labeled graph with weighted edges. You > will find such an algorithm in this paper by Gabow: > Gabow, H. N., "Two Algorithms for Generating Weighted Spanning Trees in > Order", SIAM Journal of Computing, vol. 6, no. 1, March 1977, pp. 139–150 I have a large bibliography of "k best" type problems online, at http://www.ics.uci.edu/~eppstein/bibs/kpath.bib As you might guess from the name, it largely concentrates on k shortest paths but I also include several papers on k smallest spanning trees. Gabow's paper no longer gives the fastest algorithm; there have been improvements by Frederickson [Fre-SJC-85 in my bib], myself [Epp-BIT-92], Frederickson again [Fre-SJC-97], and myself and others [EppGalIta-JACM-97]. Most of these algorithmic improvements depend on data structures for "fully persistent fully dynamic minimum spanning trees", i.e. data structures that maintain a family of graphs, create a new graph by inserting or deleting an edge from a previously created graph, and keep track of the MST of each graph. The latest dynamic MST algorithms are quite a bit faster than those in [EppGalIta-JACM-97] however unfortunately I don't remember whether they are appropriately persistent. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/