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-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. 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 contains every vertex in the graph.
- Comment
- enThe reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. 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 contains every vertex in the graph.
- Depiction
- Has abstract
- enThe reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the same paper. 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 contains 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. * For each edge, check if deleting the edge will further disconnect the graph. * Perform any deletion that does not lead to additional disconnection.
- Hypernym
- Algorithm
- Is primary topic of
- Reverse-delete algorithm
- Label
- enReverse-delete algorithm
- Link from a Wikipage to another Wikipage
- Algorithm
- Big-O notation
- Borůvka's algorithm
- Category:Graph algorithms
- Category:Spanning tree
- Dijkstra's algorithm
- File:Reverse Delete 0.svg
- File:Reverse Delete 1.svg
- File:Reverse Delete 2.svg
- File:Reverse Delete 3.svg
- File:Reverse Delete 4.svg
- File:Reverse Delete 5.svg
- File:Reverse Delete 6.svg
- Graph theory
- Greedy algorithm
- Kruskal's algorithm
- Minimum spanning tree
- Prim's algorithm
- Proceedings of the American Mathematical Society
- Symposium on Theory of Computing
- Weighted graph
- SameAs
- 4a3ax
- m.02phgw5
- Q4925151
- Reverse-delete algorithm
- Алгоритам обрнутог брисања
- Алгоритм обратного удаления
- الگوریتم حذف معکوس
- ขั้นตอนวิธีการลบย้อนกลับ
- Subject
- Category:Graph algorithms
- Category:Spanning tree
- Thumbnail
- WasDerivedFrom
- Reverse-delete algorithm?oldid=1083605955&ns=0
- WikiPageLength
- 8699
- Wikipage page ID
- 9516059
- Wikipage revision ID
- 1083605955
- WikiPageUsesTemplate
- Template:Citation
- Template:Harv
- Template:Harvtxt
- Template:Short description
- Template:Sic
