Reverse-delete algorithm


Reverse-delete algorithm

The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighed graph. If the graph is disconnected, this algorithm will find a minimum spanning tree for each disconnected part of the graph. The set of these minimum spanning trees is called a minimum spanning forest, which consists of every vertex in the graph.

This algorithm is a greedy algorithm, choosing the best choice given any situation. It is the reverse of Kruskal's algorithm, which is another greedy algorithm to find a minimum spanning tree. Kruskal’s algorithm starts with an empty graph and adds edges while the Reverse-Delete algorithm starts with the original graph and deletes edges from it. The algorithm works as follows:
* Start with graph G, which contains a list of edges E.
* Go through E in decreasing order of edge weights.
* Check if deleting current edge will further disconnect graph.
* If G is not further disconnected, delete the edge.

Proof of correctness

The Reverse-Delete algorithm ensures connectivity in the graph or graph parts before deletion. Since the algorithm only deletes edges when it does not disconnect the graph, any edge removed by the algorithm at the time of deletion was in a cycle. Since the algorithm starts from the heaviest weighted edge and continues in decreasing order, the edge removed from any cycle is the maximum edge in that cycle. Therefore, according to the definition of a minimum spanning tree, the edges removed by the algorithm are not in any minimum spanning tree.

Pseudocode

1 function ReverseDelete(edges [] "E") 2 sort "E" in decreasing order 3 Define an index "i" ← 0 4 while "i" < size("E") 5 Define edge "temp" ← "E" ["i"] 6 delete "E" ["i"] 7 if "temp.v1" is not connected to "temp.v2" 8 "E" ["i"] ← "temp" 9 "i" ← "i" + 1 10 return edges [] "E"In the above the graph is the set of edges "E" with each edge containing a weight and connected vertices "v1" and "v2".

Example

In the following example green edges are those being evaluated by the algorithm and red edges are those which have been deleted.

Running time

The algorithm can be shown to run in "O"("E" log "E" (log log "E")3) time, where "E" is the number of edges and "V" is the number of vertices. This bound is achieved as follows:
* sorting the edges by weight using a comparison sort in "O"("E" log "E") time
* "E" iterations of loop
* deleting in "O"(1) time
* connectivity checked in "O"(log"V" (log log "V")3) time harv|Thorup|2000.

Equally, the running time can be considered "O"("E" log "V" (log log "V")3) because the largest "E" can be is "V"2. Remember that log"V"2 = 2 * log"V", so "2" is a multiplicative constant that will be ignored in big-O notation.

ee also

* Kruskal's algorithm
* Prim's algorithm
* Borůvka's algorithm
* Dijkstra's algorithm

References

*citation|last1=Kleinberg|first1=Jo|first2=Éva|last2=Tardos|authorlink2=Éva Tardos|title=Algorithm Design|location=New York|publisher=Pearson Education, Inc.|year=2006.
*citation|first=Mikkel|last=Thorup|contribution=Near-optimal fully-dynamic graph connectivity|Proc. 32nd ACM Symp. Theory of Computing|year=2000|pages=343–350|doi=10.1145/335305.335345.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Kruskal's algorithm — is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is… …   Wikipedia

  • Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • David Karger — is a Professor of Computer Science and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology (MIT). He received an AB from Harvard University and a PhD in computer science… …   Wikipedia

  • Five color theorem — The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent… …   Wikipedia

  • Multiple channel cryptography — Infobox block cipher name = MCC designers = Richard Ervasti publish date = 2008 ndash;02 key size = variable block size = variable structure = SPN rounds = 2 cryptanalysis = Multiple channel cryptography (MCC) is an emerging approach to block… …   Wikipedia

  • d-ary heap — The d ary heap or d heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2.[1][2][3] Thus, a binary heap is a 2 heap. According to Tarjan[2] and Jensen et al …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия