Parallel algorithms for minimum spanning trees: Difference between revisions

Revision as of 23:16, 24 April 2021

Latest revision as of 05:49, 3 August 2025

(8 intermediate revisions by 7 users not shown)

Line 26:

One possible idea is to use <math>O(n)</math> processors to support PQ access in <math>O(1)</math> on an [[Parallel random-access machine|EREW-PRAM]] machine,<ref>{{citation

| last1 = Brodal

| firstfirst1 = Gerth Stølting

| last2 = Träff

| first2 = Jesper Larsson

Line 105:

<math>T \gets \emptyset</math>

'''while''' <math>|V| > 01</math>

<math>S \gets \emptyset</math>

'''for''' <math>v \in V</math>

Line 118:

=== Parallelisation ===

One possible parallelisation of this algorithm<ref>{{cite web |last1=Sanders |first1=Peter |title=Parallel Algorithms script |url=https://algo2.iti.kit.edu/sanders/courses/paralg18/skript.pdf |website=Parallel Algorithms KIT Homepage |access-date=25 February 2019}}</ref><ref>{{cite web |last1=Zadeh |first1=Reza |title=Distributed Algorithms and Optimization |url=https://stanford.edu/~rezab/dao/notes/lecture06/cme323_lec6.pdf |website=Distributed Algorithms and Optimization Stanford University Homepage |access-date=25 February 2019}}</ref><ref>{{cite journalbook |last1=Chun |first1=Sun |last2=Condon |first2=Anne |title=Proceedings of International Conference on Parallel Processing |chapter=Parallel implementation of Bouvka's minimum spanning tree algorithm |journal=Proceedings of International Conference on Parallel Processing |date=1996 |pages=302–308 |doi=10.1109/IPPS.1996.508073 |isbn=0-8186-7255-2 |s2cid=12710022 }}</ref> yields a [[Polylogarithmic_function|polylogarithmic]] time complexity, i.e. <math>T(m, n, p) \cdot p \in O(m \log n)</math> and there exists a constant <math>c</math> so that <math>T(m, n, p) \in O(\log^c m)</math>. Here <math>T(m, n, p)</math> denotes the runtime for a graph with <math>m</math> edges, <math>n</math> vertices on a machine with <math>p</math> processors. The basic idea is the following:

'''while''' <math>|V| > 1</math>

Line 174:

=== Complexity ===

Each iteration now needs <math>O(\frac{m}{p} + \log n)</math> time and just like in the sequential case there are <math>\log n</math> interationsiterations, resulting in a total runtime of <math>O(\log n(\frac{m}{p} + \log n))</math>. If <math>m \in \Omega(p \log^2 p)</math> the efficiency of the algorithm is in <math>\Theta(1)</math> and it is relatively efficient. If <math>m \in O(n)</math> then it is absolutely efficient.

== Further algorithms ==

Line 193:

| volume = 48

| year = 2001| citeseerx = 10.1.1.32.1554

| s2cid = 1778676

}}</ref><ref>{{citation

| last1 = Pettie | first1 = Seth

Line 207 ⟶ 208:

| last1 = Bader

| first1 = David A.

| author1-link = David A. Bader (computer scientist)

| last2 = Cong

| first2 = Guojing

Line 219 ⟶ 220:

Another challenge is the External Memory model - there is a proposed algorithm due to Dementiev et al. that is claimed to be only two to five times slower than an algorithm that only makes use of internal memory<ref>{{citation

| last1 = Dementiev
| first1 = Roman

| last2 = Sanders
| first2 = Peter

| last3 = Schultes
| first3 = Dominik

| last4 = Sibeyn
| first4 = Jop F.

| contribution = Engineering an external memory minimum spanning tree algorithm

| pages = 195–208

| title = Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)

| url = http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| year = 2004}}.</ref>

| access-date = 2019-05-24

| archive-date = 2011-08-09

| archive-url = https://web.archive.org/web/20110809075049/http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| url-status = dead

}}.</ref>

== References ==