About: Reverse-delete algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Reverse-delete algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

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.

Attributes	Values
rdf:type	software
rdfs:label	Reverse-delete algorithm (en)
rdfs:comment	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. (en)
sameAs	Reverse-delete algorithm Reverse-delete algorithm
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Harv dbt:Harvtxt dbt:Short_description dbt:Sic dbt:Graph_search_algorithm
Subject	Spanning tree Graph algorithms
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Reverse-delete_algorithm?oldid=972176968&ns=0
Wikipage page ID	9516059 (xsd:integer)
page length (characters) of wiki page	8726 (xsd:nonNegativeInteger)
Wikipage revision ID	972176968 (xsd:integer)
has abstract	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. 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Reverse-delete_algorithm
is Wikipage redirect of	Reverse-Delete algorithm
is Link from a Wikipage to another Wikipage of	Kruskal's algorithm List of algorithms Minimum spanning tree Expected linear time MST algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software