Recursive largest first algorithm - Revision history

Rhyd Lewis: /* External links */ Added link

2025-01-30T11:49:14Z

External links: Added link

← Previous revision		Revision as of 11:49, 30 January 2025
Line 37:		Line 37:

	==External links==		==External links==
			* [https://gcol.readthedocs.io/en/latest/ ''GCol''] An open-source python library for graph coloring featuring RLF.
	* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).		* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).

JJMC89 bot III: Moving :Category:Algorithms in graph theory to :Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

2024-10-12T19:57:46Z

Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4

← Previous revision		Revision as of 19:57, 12 October 2024
Line 40:		Line 40:

	[[Category:1979 in computing]]		[[Category:1979 in computing]]
	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Graph coloring]]		[[Category:Graph coloring]]

JJMC89 bot III: Moving :Category:Graph algorithms to :Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

2024-10-12T02:24:58Z

Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms

← Previous revision		Revision as of 02:24, 12 October 2024
Line 40:		Line 40:

	[[Category:1979 in computing]]		[[Category:1979 in computing]]
	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Graph coloring]]		[[Category:Graph coloring]]

Citation bot: Alter: doi. Add: s2cid, series, pmc, pmid, doi, issue. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 894/2500

2023-01-03T16:50:19Z

Alter: doi. Add: s2cid, series, pmc, pmid, doi, issue. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 894/2500

← Previous revision		Revision as of 16:50, 3 January 2023
Line 1:		Line 1:
	{{Short description\|Algorithm for graph coloring}}		{{Short description\|Algorithm for graph coloring}}

	The '''Recursive Largest First''' ('''RLF''') algorithm is a [[heuristic]] for the [[NP-hard]] [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>		The '''Recursive Largest First''' ('''RLF''') algorithm is a [[heuristic]] for the [[NP-hard]] [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|issue=6 \|pages=489–503\|doi=10.6028/jres.084.024 \|pmid=34880531 \|pmc=6756213 }}</ref>

	The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.		The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

	To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].<ref name=":1">{{Cite book\|last=Lewis\|first=R.\|date=2021\|title=A Guide to Graph Colouring: Algorithms and Applications\|publisher=Springer\|doi=		To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].<ref name=":1">{{Cite book\|last=Lewis\|first=R.\|date=2021\|title=A Guide to Graph Colouring: Algorithms and Applications\|series=Texts in Computer Science \|publisher=Springer\|doi=10.1007/978-3-030-81054-2\|isbn=978-3-030-81053-5\|s2cid=57188465 }}</ref> In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s [[chromatic number]].
	10.1007/978-3-030-81054-2\|isbn=978-3-030-81053-5}}</ref> In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s [[chromatic number]].

	==Description==		==Description==

Felix QW: /* External links */ Removed ref name causing issues

2022-01-15T15:10:57Z

External links: Removed ref name causing issues

← Previous revision		Revision as of 15:10, 15 January 2022
Line 38:		Line 38:

	==External links==		==External links==
	* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).~~<ref name=":1"/>~~		* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).

	[[Category:1979 in computing]]		[[Category:1979 in computing]]

AnomieBOT: Fixing reference errors

2022-01-13T13:49:27Z

Fixing reference errors

← Previous revision		Revision as of 13:49, 13 January 2022
Line 28:		Line 28:

	==Performance==		==Performance==
	Let <math>n</math> be the number of vertices in the graph and let <math>m</math> be the number of edges. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; however, this can be improved upon. Much of the expense of this algorithm is due to Step 2, where vertex selection is made according to the heuristic rules stated above. Indeed, each time a vertex is selected for addition to the independent set <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"></~~ref~~>		Let <math>n</math> be the number of vertices in the graph and let <math>m</math> be the number of edges. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; however, this can be improved upon. Much of the expense of this algorithm is due to Step 2, where vertex selection is made according to the heuristic rules stated above. Indeed, each time a vertex is selected for addition to the independent set <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"/>

	If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to <math>\mathcal{O}(n+m)</math>; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.<ref name=":1"></~~ref~~> It will also now be inexact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].		If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to <math>\mathcal{O}(n+m)</math>; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.<ref name=":1"/> It will also now be inexact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].

	In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"></~~ref~~>		In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"/>

	==References==		==References==
Line 38:		Line 38:

	==External links==		==External links==
	* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).<ref name=":1"></~~ref~~>		* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).<ref name=":1"/>

	[[Category:1979 in computing]]		[[Category:1979 in computing]]

Frap: Bold

2022-01-13T13:37:18Z

Bold

← Previous revision		Revision as of 13:37, 13 January 2022
Line 1:		Line 1:
	{{Short description\|Algorithm for graph coloring}}		{{Short description\|Algorithm for graph coloring}}

	The Recursive Largest First (RLF) algorithm is a [[heuristic]] for the [[NP-hard]] [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>		The '''Recursive Largest First''' ('''RLF''') algorithm is a [[heuristic]] for the [[NP-hard]] [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>

	The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.		The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.
Line 33:		Line 33:

	In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"></ref>		In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"></ref>

		⚫	==References==
		⚫	{{reflist}}

	==External links==		==External links==
	* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).<ref name=":1"></ref>		* [http://rhydlewis.eu/gcol/ ''High-Performance Graph Colouring Algorithms''] Suite of graph coloring algorithms (implemented in C++) used in the book ''[https://link.springer.com/book/10.1007/978-3-030-81054-2 A Guide to Graph Colouring: Algorithms and Applications]'' (Springer International Publishers, 2021).<ref name=":1"></ref>

⚫	== References ==

⚫	{{reflist}}

	[[Category:1979 in computing]]		[[Category:1979 in computing]]

Rhyd Lewis: Small amount of tidying, and correction of one typo.

2022-01-06T13:35:33Z

Small amount of tidying, and correction of one typo.

Curb Safe Charmer: Cleaning up accepted Articles for creation submission (AFCH 0.9.1)

2022-01-05T11:52:47Z

Cleaning up accepted Articles for creation submission (AFCH 0.9.1)

← Previous revision		Revision as of 11:52, 5 January 2022
Line 1:		Line 1:
	{{Short description\|Algorithm for graph coloring}}		{{Short description\|Algorithm for graph coloring}}

	{{Draft topics\|computing}}
	{{AfC topic\|stem}}
	{{AfC submission\|\|\|ts=20220105114143\|u=Rhyd Lewis\|ns=2}}
	The Recursive Largest First (RLF) algorithm is a [[heuristic]] for the NP-hard [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>		The Recursive Largest First (RLF) algorithm is a [[heuristic]] for the NP-hard [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>

Line 34:		Line 32:
	If the heuristics of Step 2 are replaced with random selection, then the complexity is reduced to <math>\mathcal{O}(n+m)</math>; however, this will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref>		If the heuristics of Step 2 are replaced with random selection, then the complexity is reduced to <math>\mathcal{O}(n+m)</math>; however, this will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref>

	In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher due to its higher overall complexity.<ref name=":1"></ref>		In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher due to its higher overall complexity.<ref name=":1"></ref>

	==External links==		==External links==
Line 40:		Line 38:

	== References ==		== References ==

	<!-- Inline citations added to your article will automatically display here. See https://en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
	{{reflist}}		{{reflist}}

Curb Safe Charmer: Curb Safe Charmer moved page Draft:Recursive largest first algorithm to Recursive largest first algorithm: Publishing accepted Articles for creation submission (AFCH 0.9.1)

2022-01-05T11:52:46Z

Curb Safe Charmer moved page Draft:Recursive largest first algorithm to Recursive largest first algorithm: Publishing accepted Articles for creation submission (AFCH 0.9.1)

← Previous revision	Revision as of 11:52, 5 January 2022
(No difference)

← Previous revision		Revision as of 13:35, 6 January 2022
Line 1:		Line 1:
	{{Short description\|Algorithm for graph coloring}}		{{Short description\|Algorithm for graph coloring}}

	The Recursive Largest First (RLF) algorithm is a [[heuristic]] for the NP-hard [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>		The Recursive Largest First (RLF) algorithm is a [[heuristic]] for the [[NP-hard]] [[graph coloring problem]]. It was originally proposed by Frank Leighton in 1979.<ref name=":0">{{Cite journal\|last=Leighton\|first=F.\|date=1979\|title=A graph coloring algorithm for large scheduling problems\|journal=Journal of Research of the National Bureau of Standards\|volume=84\|pages=489–503}}</ref>

	The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying an [[~~Independent_set_(graph_theory)\|~~independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.		The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a [[maximal independent set]] of vertices in the graph, assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

	To ~~try and~~ form high-quality solutions (solutions using as few colors ~~as possible~~), the RLF algorithm uses specialized ~~heuristics~~ to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].<ref name=":1">{{Cite book\|last=Lewis\|first=R.\|date=2021\|title=A Guide to Graph Colouring: Algorithms and Applications\|publisher=Springer\|doi=		To form high-quality solutions (solutions using few colors), the RLF algorithm uses specialized heuristic rules to try to identify "good quality" independent sets. These heuristics make the RLF algorithm exact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].<ref name=":1">{{Cite book\|last=Lewis\|first=R.\|date=2021\|title=A Guide to Graph Colouring: Algorithms and Applications\|publisher=Springer\|doi=
	10.1007/978-3-030-81054-2\|isbn=978-3-030-81053-5}}</ref> In general, however, the algorithm is approximate, and may well return solutions ~~using~~ more colors than the graph’s [[chromatic number]].		10.1007/978-3-030-81054-2\|isbn=978-3-030-81053-5}}</ref> In general, however, the algorithm is approximate and may well return solutions that use more colors than the graph’s [[chromatic number]].

	==Description==		==Description==
	The algorithm can be described by the following three steps. At the end of this process, <math>\mathcal{S}</math> gives a partition of the vertices representing a feasible <math>\|\mathcal{S}\|</math>-colouring of the graph <math>G</math>.		The algorithm can be described by the following three steps. At the end of this process, <math>\mathcal{S}</math> gives a partition of the vertices representing a feasible <math>\|\mathcal{S}\|</math>-colouring of the graph <math>G</math>.

	# Let <math>\mathcal{S}=\emptyset</math> be an empty solution, ~~and~~ let <math>G=(V,E)</math> be the graph we wish to color, comprising a vertex set <math>V</math> and an edge set <math>E</math>.		# Let <math>\mathcal{S}=\emptyset</math> be an empty solution. Also, let <math>G=(V,E)</math> be the graph we wish to color, comprising a vertex set <math>V</math> and an edge set <math>E</math>.
	# Identify a [[maximal independent set]] <math>S\subseteq V</math>. To do this:		# Identify a [[maximal independent set]] <math>S\subseteq V</math>. To do this:
	## The first vertex added to <math>S</math> should be the vertex in <math>G</math> that has the largest number of neighbors.		## The first vertex added to <math>S</math> should be the vertex in <math>G</math> that has the largest number of neighbors.
	## Subsequent vertices added to <math>S</math> should be chosen as those that ~~are~~ (a) not currently adjacent to any vertex in <math>S</math>, and (b) have a maximal number of neighbors that are adjacent to vertices in <math>S</math>. Ties in condition (b) can be broken by selecting the vertex with the minimum number of neighbors not in <math>S</math>. Vertices are added to <math>S</math> in this way until it is impossible to add further vertices.		## Subsequent vertices added to <math>S</math> should be chosen as those that (a) are not currently adjacent to any vertex in <math>S</math>, and (b) have a maximal number of neighbors that are adjacent to vertices in <math>S</math>. Ties in condition (b) can be broken by selecting the vertex with the minimum number of neighbors not in <math>S</math>. Vertices are added to <math>S</math> in this way until it is impossible to add further vertices.
	# Now set <math>\mathcal{S}=\mathcal{S}\cup \{S\}</math> and remove the vertices of <math>S</math> from <math>G</math>. If <math>G</math> still contains vertices, then return to Step 2; otherwise end.		# Now set <math>\mathcal{S}=\mathcal{S}\cup \{S\}</math> and remove the vertices of <math>S</math> from <math>G</math>. If <math>G</math> still contains vertices, then return to Step 2; otherwise end.

Line 28:		Line 28:

	==Performance==		==Performance==
	Let <math>n</math> be the number of vertices in the graph and <math>m</math> be the number of ~~colors~~. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; however, this can be improved upon. Much of the expense of this algorithm is due to Step 2, where vertex selection is made according to the heuristic rules stated above. Indeed, each time a vertex is selected for addition to the independent set <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"></ref>		Let <math>n</math> be the number of vertices in the graph and let <math>m</math> be the number of edges. Using [[big O notation]], in his original publication Leighton states the complexity of RLF to be <math>\mathcal{O}(n^3)</math>; however, this can be improved upon. Much of the expense of this algorithm is due to Step 2, where vertex selection is made according to the heuristic rules stated above. Indeed, each time a vertex is selected for addition to the independent set <math>S</math>, information regarding the neighbors needs to be recalculated for each uncolored vertex. These calculations can be performed in <math>\mathcal{O}(m)</math> time, meaning that the overall complexity of RLF is <math>\mathcal{O}(mn)</math>.<ref name=":1"></ref>

	If the heuristics of Step 2 are replaced with random selection, then the complexity is ~~reduced~~ to <math>\mathcal{O}(n+m)</math>; however, ~~this~~ will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref>		If the heuristics of Step 2 are replaced with random selection, then the complexity of this algorithm reduces to <math>\mathcal{O}(n+m)</math>; however, the resultant algorithm will usually return lower quality solutions compared to those of RLF.<ref name=":1"></ref> It will also now be inexact for [[bipartite graph\|bipartite]], [[cycle graph\|cycle]], and [[wheel graph\|wheel graphs]].

	In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher due to its higher overall complexity.<ref name=":1"></ref>		In an empirical comparison by Lewis in 2021, RLF was shown to produce significantly better vertex colorings than alternative heuristics such as the <math>\mathcal{O}(n+m)</math> [[Greedy coloring\|greedy algorithm]] and the <math>\mathcal{O}((n + m) \lg n)</math> [[DSatur]] algorithm on [[random graph\|random graphs]]. However, runtimes with RLF were also seen to be higher than these alternatives due to its higher overall complexity.<ref name=":1"></ref>

	==External links==		==External links==