Minimum Spammning Trees

Humor

Etc

Consider a directed graph, G(N,A), where N and A are the set of nodes and arcs, respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N|=n and |A|=m. The problem is to find a rooted directed spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted directed spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.

The Directed Minimum Spanning Tree Problem

Chu and Liu [2], Edmonds [3], and Bock [4] have independently given efficient algorithms for finding the MST on a directed graph. The Chu-Liu and Edmonds algorithms are virtually identical; the Bock algorithm is similar but stated on matrices instead of on graphs. Furthermore, a distributed algorithm is given by Humblet [5]. In the sequel, we shall briefly illustrate the Chu-Liu/Edmonds algorithm, following by a comprehensive example (due to [1]). Reader can also refer to [6] [7] for an efficient implementation, O(mlogn) and O(n^2) for dense graph, of this algorithm.
Chu-Liu/Edmonds Algorithm
1. Discard the arcs entering the root if any; For each node other than the root, select the entering arc with the smallest cost; Let the selected n-1 arcs be the set S.
2. If no cycle formed, G(N,S) is a MST. Otherwise, continue.
3. For each cycle formed, contract the nodes in the cycle into a pseudo-node (k), and modify the cost of each arc which enters a node (j) in the cycle from some node (i) outside the cycle according to the following equation.
  c(i,k)=c(i,j)-(c(x(j),j)-min_{j}(c(x(j),j))
  where c(x(j),j) is the cost of the arc in the cycle which enters j.
4. For each pseudo-node, select the entering arc which has the smallest modified cost; Replace the arc which enters the same real node in S by the new selected arc.
5. Go to step 2 with the contracted graph.

A Linear Algorithm for Analysis of Minimum Spanning and.. - Booth, Westbrook (1992) (9 citations) (Correct)

....list. We call this embedding dependent depthfirst search topological. Figure 1 gives an example of an embedded planar graph and spanning tree with preorder and postorder numbering. We denote the preorder and postorder numbers of v by pre(v) and post(v) respectively. It is well known (see e.g. [17]) that for any pair u and v of vertices, v is an ancestor of u if and only if pre(v) pre(u) and post(u) post(v) Let f be a non tree edge fu; vg. We denote by nca(f) the nearest common ancestor of u and v. Edge f is a potential critical edge for every vertex on the tree path connecting u and v, ....

R. E. Tarjan. Finding dominators in directed graphs. SIAM J. Comput., 3, 1974.

Graph Theory Lecture Notes 16 Minimum Spanning Trees

NIST: minimum spanning tree

Design and Analysis of Computer Algorithms

minimum spanning tree algorithms Kruskal and Prim algorithms covered.

Data Structures and Algorithms Graph Algorithms 10.1 Minimum Spanning Trees

Suppose we have a group of islands that we wish to link with bridges so that it is possible to travel from one island to any other in the group. Further suppose that (as usual) our government wishes to spend the absolute minimum amount on this project (because other factors like the cost of using, maintaining, etc, these bridges will probably be the responsibility of some future government :-). The engineers are able to produce a cost for a bridge linking each possible pair of islands. The set of bridges which will enable one to travel from any island to any other at minimum capital cost to the government is the minimum spanning tree.

Minimum-Cost Spanning Trees
... The minimal subgraph of a connected graph is called a spanning tree: Definition ...
Figure: An undirected graph and three spanning trees. According ...
www.brpreiss.com/books/opus5/html/page573.html - 11k - Cached - Similar pages

Minimum Spanning Trees
... point set defines a complete graph, with edge assigned a weight equal to the distance
from to . Additional applications of minimum spanning trees are discussed ...
www2.toki.or.id/book/ AlgDesignManual/BOOK/BOOK2/NODE73.HTM - 8k - Cached - Similar pages
[ More results from www2.toki.or.id ]

Minimum Spanning Tree -- from MathWorld
Minimum Spanning Tree. The minimum spanning tree of a weighted graph is a set of
edges of minimum total weight which form a spanning tree of the graph. ...
mathworld.wolfram.com/MinimumSpanningTree.html - 19k - Cached - Similar pages

Spanning Tree -- from MathWorld
... A count of the spanning trees of a graph can be found using the command
NumberOfSpanningTrees[g] in the Mathematica add-on package DiscreteMath`Combinatorica ...
mathworld.wolfram.com/SpanningTree.html - 20k - Cached - Similar pages

Science Fair Projects - Minimum spanning tree
... tree and connects all the vertices together. A single graph can have many
different spanning trees. We can also assign a weight to ...
www.all-science-fair-projects.com/science_ fair_projects_encyclopedia/Minimum_spanning_tree - 17k - Cached - Similar pages

1.4.3 Minimum Spanning Tree
... The Algorithm Design Manual: The minimum spanning tree (MST) of a graph defines
the cheapest subset of edges that keeps the graph in one connected component. ...
www.cs.sunysb.edu/~algorith/ files/minimum-spanning-tree.shtml - 5k - Oct 31, 2004 - Cached - Similar pages

Definition of Spanning tree (mathematics)
... Cayley's theorem can be used to find the number of labelled spanning trees in a
complete graph. There are exactly n power(n-2) labelled trees with n vertices. ...
www.wordiq.com/definition/Spanning_tree_(mathematics) - 10k - Cached - Similar pages

[PDF] 7.2. Spanning Trees 7.2.1. Spanning Trees. A tree T is a spanning ...
File Format: PDF/Adobe Acrobat - View as HTML
... Spanning tree. Every connected graph has a spanning tree which can be obtained
by removing edges until the resulting graph becomes acyclic. ...
www.math.northwestern.edu/~mlerma/ courses/cs310/notes/dm-spanning.pdf - Similar pages

Undirected Graphs and Minimum Spanning Trees
The Minimum Spanning Tree of an Undirected Graph. ... It repeatedly joins two trees
together until a spanning tree of the entire given graph remains. ...
www.csse.monash.edu.au/ ~lloyd/tildeAlgDS/Graph/Undirected/ - 31k - Cached - Similar pages

Info on Spanning Trees of a Connected Graph
... The tree graph of G, denoted T(G), is the graph whose vertices are the spanning
trees of G and whose edges join those spanning trees that differ by an edge ...
www.theory.csc.uvic.ca/~cos/inf/subg/Spanning.html - 6k - Oct 31, 2004 - Cached - Similar pages

Copyright © 1996-2007 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. Submit comments This document is an industrial compilation designed and created exclusively for educational use and is placed under the copyright of the Open Content License(OPL). Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

Standard disclaimer: The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.

Last modified: February 28, 2008