Minimum Spammning Trees

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.

• Kruskal Step by Step
• Tutorial Kruskal
• Interactive Kruskal's Algorithm

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

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March, 12, 2019