Parallel algorithms for minimum spanning trees - Revision history

2600:4041:4AB:A900:99AA:65FE:1187:51EA: minor type in pseudocode correction

2023-07-31T00:04:16Z

minor type in pseudocode correction

← Previous revision		Revision as of 00:04, 31 July 2023
Line 105:		Line 105:

	<math>T \gets \emptyset</math>		<math>T \gets \emptyset</math>
	'''while''' <math>\|V\| > 0</math>		'''while''' <math>\|V\| > 1</math>
	<math>S \gets \emptyset</math>		<math>S \gets \emptyset</math>
	'''for''' <math>v \in V</math>		'''for''' <math>v \in V</math>

Citation bot: Alter: title, template type. Add: s2cid, chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1341/2384

2023-07-24T23:45:04Z

Alter: title, template type. Add: s2cid, chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1341/2384

← Previous revision		Revision as of 23:45, 24 July 2023
Line 26:		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		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		\| last1 = Brodal
	\| ~~first~~ = Gerth Stølting		\| first1 = Gerth Stølting
	\| last2 = Träff		\| last2 = Träff
	\| first2 = Jesper Larsson		\| first2 = Jesper Larsson
Line 118:		Line 118:
	=== Parallelisation ===		=== 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 ~~journal~~ \|last1=Chun \|first1=Sun \|last2=Condon \|first2=Anne \|title=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 }}</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:		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 book \|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 \|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>		'''while''' <math>\|V\| > 1</math>
Line 193:		Line 193:
	\| volume = 48		\| volume = 48
	\| year = 2001\| citeseerx = 10.1.1.32.1554		\| year = 2001\| citeseerx = 10.1.1.32.1554
			\| s2cid = 1778676
	}}</ref><ref>{{citation		}}</ref><ref>{{citation
	\| last1 = Pettie \| first1 = Seth		\| last1 = Pettie \| first1 = Seth

Keystone18: link fixed

2023-05-06T21:31:13Z

link fixed

← Previous revision		Revision as of 21:31, 6 May 2023
Line 207:		Line 207:
	\| last1 = Bader		\| last1 = Bader
	\| first1 = David A.		\| first1 = David A.
	\| author1-link = David A. Bader		\| author1-link = David Bader (computer scientist)
	\| last2 = Cong		\| last2 = Cong
	\| first2 = Guojing		\| first2 = Guojing

David Eppstein: Reverted edits by Keystone18 (talk) to last version by Flod logic

2022-09-21T04:28:18Z

Reverted edits by Keystone18 (talk) to last version by Flod logic

← Previous revision		Revision as of 04:28, 21 September 2022
Line 207:		Line 207:
	\| last1 = Bader		\| last1 = Bader
	\| first1 = David A.		\| first1 = David A.
	\| author1-link = David Bader		\| author1-link = David A. Bader
	\| last2 = Cong		\| last2 = Cong
	\| first2 = Guojing		\| first2 = Guojing

Keystone18 at 01:56, 21 September 2022

2022-09-21T01:56:28Z

← Previous revision		Revision as of 01:56, 21 September 2022
Line 207:		Line 207:
	\| last1 = Bader		\| last1 = Bader
	\| first1 = David A.		\| first1 = David A.
	\| author1-link = David A. Bader		\| author1-link = David Bader
	\| last2 = Cong		\| last2 = Cong
	\| first2 = Guojing		\| first2 = Guojing

Flod logic: /* Complexity */ spelling

2021-06-14T18:09:16Z

Complexity: spelling

← Previous revision		Revision as of 18:09, 14 June 2021
Line 174:		Line 174:
	=== Complexity ===		=== 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> ~~interations~~, 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.		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> iterations, 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 ==		== Further algorithms ==

2401:4900:43A2:E3D:153E:477C:7DC5:1745: /* Further algorithms */

2021-04-24T23:16:21Z

Further algorithms

← Previous revision		Revision as of 23:16, 24 April 2021
Line 204:		Line 204:
	\| volume = 31		\| volume = 31
	\| year = 2002\| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf		\| year = 2002\| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf
	}}</ref> Bader ~~und~~ Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm.<ref>{{citation		}}</ref> Bader and Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm.<ref>{{citation
	\| last1 = Bader		\| last1 = Bader
	\| first1 = David A.		\| first1 = David A.

WikiCleanerBot: v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2021-01-06T21:03:40Z

v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 21:03, 6 January 2021
Line 6:		Line 6:
	If <math>G</math> is [[Glossary_of_graph_theory_terms#unweighted_graph\|edge-unweighted]] every spanning tree possesses the same number of edges and thus the same weight. In the [[Glossary_of_graph_theory_terms#weighted_graph\|edge-weighted]] case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of <math>G</math>, is called a [[minimum spanning tree]] (MST). It is not necessarily unique. More generally, graphs that are not necessarily [[Glossary_of_graph_theory_terms#connected\|connected]] have minimum spanning [[Tree_(graph_theory)#Forest\|forests]], which consist of a [[Union_(set_theory)\|union]] of MSTs for each [[Connected_component_(graph_theory)\|connected component]].		If <math>G</math> is [[Glossary_of_graph_theory_terms#unweighted_graph\|edge-unweighted]] every spanning tree possesses the same number of edges and thus the same weight. In the [[Glossary_of_graph_theory_terms#weighted_graph\|edge-weighted]] case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of <math>G</math>, is called a [[minimum spanning tree]] (MST). It is not necessarily unique. More generally, graphs that are not necessarily [[Glossary_of_graph_theory_terms#connected\|connected]] have minimum spanning [[Tree_(graph_theory)#Forest\|forests]], which consist of a [[Union_(set_theory)\|union]] of MSTs for each [[Connected_component_(graph_theory)\|connected component]].

	As finding MSTs is a widespread problem in graph theory, there exist many [[Sequential_algorithm\|sequential algorithms]] for solving it. Among them are [[Prim's algorithm\|Prim's]], [[Kruskal's algorithm\|Kruskal's]] and [[Borůvka's algorithm\|Borůvka's]] algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of <math>E</math> is iteratively grown until a valid MST has been discovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), [[Time_complexity\|performance]] is a key factor. One option of improving it is by [[Parallel algorithm\|parallelising]] known [[Minimum_spanning_tree#Algorithms\|MST algorithms]]<ref>{{cite book \|last1=Sanders \|last2=Dietzfelbinger \|last3=Martin \|last4=Mehlhorn \|last5=Kurt \|last6=Peter \|title=Algorithmen und Datenstrukturen Die Grundwerkzeuge \|publisher=Springer Vieweg \|isbn=978-3-642-05472-3\|date=2014-06-10 }}</ref>.		As finding MSTs is a widespread problem in graph theory, there exist many [[Sequential_algorithm\|sequential algorithms]] for solving it. Among them are [[Prim's algorithm\|Prim's]], [[Kruskal's algorithm\|Kruskal's]] and [[Borůvka's algorithm\|Borůvka's]] algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of <math>E</math> is iteratively grown until a valid MST has been discovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), [[Time_complexity\|performance]] is a key factor. One option of improving it is by [[Parallel algorithm\|parallelising]] known [[Minimum_spanning_tree#Algorithms\|MST algorithms]].<ref>{{cite book \|last1=Sanders \|last2=Dietzfelbinger \|last3=Martin \|last4=Mehlhorn \|last5=Kurt \|last6=Peter \|title=Algorithmen und Datenstrukturen Die Grundwerkzeuge \|publisher=Springer Vieweg \|isbn=978-3-642-05472-3\|date=2014-06-10 }}</ref>

	== Prim's algorithm ==		== Prim's algorithm ==
Line 24:		Line 24:
	It is important to note that the loop is inherently sequential and can not be properly parallelised. This is the case, since the lightest edge with one endpoint in <math>S</math> and on in <math>V \setminus S</math> might change with the addition of edges to <math>T</math>. Thus no two selections of a lightest edge can be performed at the same time. However, there do exist some attempts at [[Prim%27s algorithm#Parallel Algorithm\|parallelisation]].		It is important to note that the loop is inherently sequential and can not be properly parallelised. This is the case, since the lightest edge with one endpoint in <math>S</math> and on in <math>V \setminus S</math> might change with the addition of edges to <math>T</math>. Thus no two selections of a lightest edge can be performed at the same time. However, there do exist some attempts at [[Prim%27s algorithm#Parallel Algorithm\|parallelisation]].

	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		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		\| last1 = Brodal
	\| first = Gerth Stølting		\| first = Gerth Stølting
Line 38:		Line 38:
	\| pages = 4–21\| doi = 10.1006/jpdc.1998.1425		\| pages = 4–21\| doi = 10.1006/jpdc.1998.1425
	\| citeseerx = 10.1.1.48.3272		\| citeseerx = 10.1.1.48.3272
	}}</ref>, thus lowering the total runtime to <math>O(n + m)</math>.		}}</ref> thus lowering the total runtime to <math>O(n + m)</math>.

	== Kruskal's algorithm ==		== Kruskal's algorithm ==
Line 69:		Line 69:
	\| journal = Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics		\| journal = Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics
	\| pages = 52–61\| citeseerx = 10.1.1.218.2574		\| pages = 52–61\| citeseerx = 10.1.1.218.2574
	}}</ref><ref>{{cite web \|last1=Sanders \|first1=Peter \|title=Algorithm Engineering script \|url=http://algo2.iti.kit.edu/sanders/courses/algen17/skript.pdf \|website=Algorithm Engineering KIT Homepage \|access-date=25 February 2019}}</ref>. The basic idea behind Filter-Kruskal is to partition the edges in a similar way to [[quicksort]] and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below.		}}</ref><ref>{{cite web \|last1=Sanders \|first1=Peter \|title=Algorithm Engineering script \|url=http://algo2.iti.kit.edu/sanders/courses/algen17/skript.pdf \|website=Algorithm Engineering KIT Homepage \|access-date=25 February 2019}}</ref> The basic idea behind Filter-Kruskal is to partition the edges in a similar way to [[quicksort]] and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below.

	filterKruskal(<math>G</math>):		filterKruskal(<math>G</math>):
Line 204:		Line 204:
	\| volume = 31		\| volume = 31
	\| year = 2002\| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf		\| year = 2002\| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf
	}}</ref>. Bader und Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm<ref>{{citation		}}</ref> Bader und Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm.<ref>{{citation
	\| last1 = Bader		\| last1 = Bader
	\| first1 = David A.		\| first1 = David A.
Line 216:		Line 216:
	\| title = Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs		\| title = Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs
	\| volume = 66		\| volume = 66
	\| year = 2006}}</ref>.		\| year = 2006}}</ref>

	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		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

Monkbot: Task 18 (cosmetic): eval 11 templates: hyphenate params (3×);

2021-01-03T23:23:51Z

Task 18 (cosmetic): eval 11 templates: hyphenate params (3×);

← Previous revision		Revision as of 23:23, 3 January 2021
Line 69:		Line 69:
	\| journal = Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics		\| journal = Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics
	\| pages = 52–61\| citeseerx = 10.1.1.218.2574		\| pages = 52–61\| citeseerx = 10.1.1.218.2574
	}}</ref><ref>{{cite web \|last1=Sanders \|first1=Peter \|title=Algorithm Engineering script \|url=http://algo2.iti.kit.edu/sanders/courses/algen17/skript.pdf \|website=Algorithm Engineering KIT Homepage \|~~accessdate~~=25 February 2019}}</ref>. The basic idea behind Filter-Kruskal is to partition the edges in a similar way to [[quicksort]] and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below.		}}</ref><ref>{{cite web \|last1=Sanders \|first1=Peter \|title=Algorithm Engineering script \|url=http://algo2.iti.kit.edu/sanders/courses/algen17/skript.pdf \|website=Algorithm Engineering KIT Homepage \|access-date=25 February 2019}}</ref>. The basic idea behind Filter-Kruskal is to partition the edges in a similar way to [[quicksort]] and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below.

	filterKruskal(<math>G</math>):		filterKruskal(<math>G</math>):
Line 118:		Line 118:
	=== Parallelisation ===		=== 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 \|~~accessdate~~=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 \|~~accessdate~~=25 February 2019}}</ref><ref>{{cite journal \|last1=Chun \|first1=Sun \|last2=Condon \|first2=Anne \|title=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 }}</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:		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 journal \|last1=Chun \|first1=Sun \|last2=Condon \|first2=Anne \|title=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 }}</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>		'''while''' <math>\|V\| > 1</math>

Arjayay: Sp

2020-09-21T14:18:18Z

← Previous revision		Revision as of 14:18, 21 September 2020
Line 170:		Line 170:
	<math>E' \gets \{(f(pred[v]), f(pred[w]), c, e_{old}): (v, w) \in E \land pred[v] \neq pred[w]\}</math>		<math>E' \gets \{(f(pred[v]), f(pred[w]), c, e_{old}): (v, w) \in E \land pred[v] \neq pred[w]\}</math>

	Finding the bijective function is possible in <math>O(\frac{n}{p} + \log p)</math> using a prefix sum. As we now have a new set of vertices and edges the adjacency array must be ~~rebuild~~, which can be done using Integersort on <math>E'</math> in <math>O(\frac{m}{p} + \log p)</math> time.		Finding the bijective function is possible in <math>O(\frac{n}{p} + \log p)</math> using a prefix sum. As we now have a new set of vertices and edges the adjacency array must be rebuilt, which can be done using Integersort on <math>E'</math> in <math>O(\frac{m}{p} + \log p)</math> time.

	=== Complexity ===		=== Complexity ===