The reverse-delete algorithm is a graph theory algorithm used to obtain a minimum spanning tree, or for a disconnected graph a minimum spanning forest touching every vertex, from a connected, edge-weighted graph. It first appeared in a 1956 paper by Joseph Kruskal, though it should not be confused with Kruskal's algorithm from the same paper: Kruskal's algorithm is a greedy algorithm that starts with an empty graph and adds edges, while the reverse-delete algorithm starts with the original graph and deletes edges from it in decreasing order of weight whenever a deletion would not further disconnect the graph.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 2 Classification
Design Technique Connections
In Field
Source Reverse-Delete Algorithm (Wikipedia)
Uses Design Technique
Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.
Sources
1. Reverse-Delete Algorithm (Wikipedia)
Wikipedia lead/infobox
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
In Field: Algorithms and Complexity Theory, Lead sentence
reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph.
View the Source2. Wikidata: Reverse-Delete Algorithm
Wikidata Q4925151, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.