About: Expected linear time MST algorithm

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

About: Expected linear time MST algorithm Goto Sponge NotDistinct Permalink

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

The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance.

Attributes	Values
rdfs:label	Expected linear time MST algorithm (en)
rdfs:comment	The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance. (en)
sameAs	Expected linear time MST algorithm Expected linear time MST algorithm
dbp:wikiPageUsesTemplate	dbt:Reflist
Subject	Randomized algorithms Spanning tree
thumbnail	wiki-commons:Special:FilePath/Boruvka_Step_1.svg?width=300
foaf:depiction
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm?oldid=1051508644&ns=0
Wikipage page ID	35516383 (xsd:integer)
page length (characters) of wiki page	14376 (xsd:nonNegativeInteger)
Wikipage revision ID	1051508644 (xsd:integer)
Link from a Wikipage to another Wikipage	Greedy algorithm Vertex (graph theory) Binary tree Borůvka's algorithm Randomized algorithms Spanning tree Geometric series Glossary of graph theory David Karger Divide-and-conquer algorithm Kruskal's algorithm Prim's algorithm Robert Tarjan Time complexity Minimum spanning tree Reverse-delete algorithm Graph Expected value Negative binomial distribution Randomized algorithm Recursion (computer science)
has abstract	The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance. Deterministic algorithms that find the minimum spanning tree include Prim's algorithm, Kruskal's algorithm, reverse-delete algorithm, and Borůvka's algorithm. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm
is Link from a Wikipage to another Wikipage of	Minimum spanning tree
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/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