Live briefing
Everything about Reverse-delete algorithm
Minimum spanning forest algorithm that greedily deletes edges
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 Kruskal (1956), 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. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Reverse-delete algorithmA 5-minute orientation
- Skim a recent paper: Penerapan Algoritma Reverse-Delete dalam Menentukan Minimum Spanning Tree Pada Jaringan Pipa PERUMDA Air Minum Tirta Mayang di Perumahan SunderlandInfluential work since 2022
- Pick up a classic book: Data structures & algorithms in JavaThe most-reprinted book on the subject
- Read the landmark paper: An Efficient Implementation of Kruskal's and Reverse-Delete Minimum Spanning Tree AlgorithmCited 1 times
- Go sideways: Kruskal's algorithmA closely related topic
- Go sideways: Prim's algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
An Efficient Implementation of Kruskal's and Reverse-Delete Minimum Spanning Tree Algorithm
Linear Bottleneck Assignment Problem Based on Reverse-delete Algorithm
🆕 Influential since 2022
📚 Books worth reading
Data structures & algorithms in JavaRobert Lafore · 2003
Information and Communications SecurityTat Wing Chim · 2012
Principles of gene manipulation and genomicsS. B. Primrose · 2006
Data structures using C++D. S. Malik · 2010
Data Structures and Algorithms in JavaMichael T. Goodrich, Roberto Tamassia · 2014
Murach's Python ProgrammingMichael Urban, Joel Murach · 2016
Data structuresRichard F Gilberg · 2001
BIOINFORMATICS ALGORITHMS,VOL.IIPhillip Compeau, Pavel Pevzner · 2015
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.…
- Prim's algorithm In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset…
- Minimum spanning tree In graph theory, a minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph…
- Minimum bottleneck spanning tree In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible…
- Expected linear time MST algorithm The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices…
- Borůvka's algorithm Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not…
- Distributed minimum spanning tree The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where…
- Parallel algorithms for minimum spanning trees In graph theory a minimum spanning tree (MST) T {\displaystyle T} of a graph G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n}…