This HTML5 document contains 51 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n12http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
n17https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n5http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Prim's_algorithm
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Spanning_tree_(disambiguation)
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
dbo:wikiPageDisambiguates
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Distributed_minimum_spanning_tree
rdf:type
yago:Act100030358 yago:Event100029378 yago:WikicatDistributedAlgorithms yago:Procedure101023820 yago:Abstraction100002137 yago:PsychologicalFeature100023100 yago:Algorithm105847438 yago:Activity100407535 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label
Distributed minimum spanning tree
rdfs:comment
The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
foaf:depiction
n5:Minimum_spanning_tree.svg
dcterms:subject
dbc:Distributed_algorithms dbc:Spanning_tree
dbo:wikiPageID
6183392
dbo:wikiPageRevisionID
1123786407
dbo:wikiPageWikiLink
dbr:Message_passing dbr:Robert_G._Gallager dbc:Distributed_algorithms n12:Minimum_spanning_tree.svg dbr:Distributed_computing dbc:Spanning_tree dbr:Broadcasting_(computing) dbr:Distributed_algorithm dbr:Graph_theory dbr:FIFO_(computing_and_electronics) dbr:Borůvka's_algorithm dbr:Prim's_algorithm dbr:Kruskal's_algorithm dbr:Minimum_spanning_tree
owl:sameAs
wikidata:Q5283163 freebase:m.0fvln9 dbpedia-fa:درخت_پوشای_مینیمم_توزیع_شده n17:4imrq yago-res:Distributed_minimum_spanning_tree
dbo:thumbnail
n5:Minimum_spanning_tree.svg?width=300
dbo:abstract
The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network. The problem was first suggested and solved in time in 1983 by Gallager et al., where is the number of vertices in the graph. Later, the solution was improved to and finally where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be
prov:wasDerivedFrom
wikipedia-en:Distributed_minimum_spanning_tree?oldid=1123786407&ns=0
dbo:wikiPageLength
15496
foaf:isPrimaryTopicOf
wikipedia-en:Distributed_minimum_spanning_tree
Subject Item
dbr:Otakar_Borůvka
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Spanning_Tree_Protocol
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Minimum_spanning_tree
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Multiple_Spanning_Tree_Protocol
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
Subject Item
dbr:Distributed_Minimim_Spanning_Tree
dbo:wikiPageWikiLink
dbr:Distributed_minimum_spanning_tree
dbo:wikiPageRedirects
dbr:Distributed_minimum_spanning_tree
Subject Item
wikipedia-en:Distributed_minimum_spanning_tree
foaf:primaryTopic
dbr:Distributed_minimum_spanning_tree