|
}}.</ref> (Perhatikan bahwa masalah ini tidak terkait dengan pohon rentang ''k''-minimum.)
[[Pohon rentangrentangan minimun Euclidean]] adalah pohon rentang dari graf dengan bobot tepi yang sesuai dengan jarak Euclidean antara simpul yang merupakan titik pada bidang (atau ruang).
[[pohon rentangan minimum rectilinear]] adalah pohon rentang dari grafik dengan bobot tepi yang sesuai dengan [[jarak bujursangkar]] antara simpul yang merupakan titik dalam bidang (atau ruang).
The [[rectilinear minimum spanning tree]] is a spanning tree of a graph with edge weights corresponding to the [[rectilinear distance]] between vertices which are points in the plane (or space).
Dalam [[komputasi terdistribusi|model terdistribusi]], di mana setiap node dianggap sebagai komputer dan tidak ada node yang tahu apa pun kecuali tautan yang terhubung sendiri, seseorang dapat mempertimbangkan [[pohon rentang minimum terdistribusi]]. Definisi matematis dari masalahnya adalah sama tetapi ada pendekatan yang berbeda untuk suatu solusi.
In the [[distributed computing|distributed model]], where each node is considered a computer and no node knows anything except its own connected links, one can consider [[distributed minimum spanning tree]]. The mathematical definition of the problem is the same but there are different approaches for a solution.
The [[capacitatedPohon rentangan minimum spanning treeberkapasitas]]] isadalah apohon treeyang thatmemiliki hassimpul ayang marked nodeditandai (originasal, oratau root) anddan eachmasing-masing ofsubtree theyang subtreesmelekat attached to thepada node containstidak nolebih moredari than anode ''c'' nodes. ''c'' isdisebut calledkapasitas a tree capacitypohon. SolvingMemecahkan CMST optimallysecara optimal isadalah [[NP-hard]],<ref>{{citation
| last1 = Jothi | first1 = Raja
| last2 = Raghavachari | first2 = Balaji
| year = 2005
| doi=10.1145/1103963.1103967
}}</ref>
}}</ref> but good heuristics such as Esau-Williams and Sharma produce solutions close to optimal in polynomial time.
The [[degree-constrainedPohon spanningrentangan treedrajat minimum|degreeDerajat constrainedbatas minimumpohon spanningyang treedibatasi minimum]] isadalah a minimumpohon spanning treeminimum indi whichmana eachsetiap vertextitik isterhubung connectedke totidak nolebih more thandari ''d'' othersimpul verticeslainnya, foruntuk somebeberapa givenangka numbertertentu '' d ''. The caseKasus '' d '' = 2 isadalah akasus specialkhusus case of thedari [[travelingmasalah salesmanpenjual problemkeliling]], sojadi thetingkat degreebatasan constrainedpohon rentang minimum spanning tree isadalah [[NP-hard]] insecara generalumum.
For [[directed graph]]s, the minimum spanning tree problem is called the [[Arborescence (graph theory)|Arborescence]] problem and can be solved in quadratic time using the [[Chu–Liu/Edmonds algorithm]].
| 