MaxCliqueDyn algorithm - Revision history

178.197.203.0: Fix formatting

2024-12-23T11:38:36Z

Fix formatting

← Previous revision		Revision as of 11:38, 23 December 2024
Line 48:		Line 48:
	'''end while'''		'''end while'''

	where ''Q'' is a set of vertices of the currently growing clique, ''Q''<sub>max</sub> is a set of vertices of the largest clique currently found, ''R'' is a set of candidate vertices, Γ(p) is the set of all vertices that are adjacent to p, and ''C'' its corresponding set of color classes. The MaxClique algorithm recursively searches for a maximum clique by adding and removing vertices to and from ''Q''.		where ''Q'' is a set of vertices of the currently growing clique, ''Q''<sub>max</sub> is a set of vertices of the largest clique currently found, ''R'' is a set of candidate vertices, ''Γ(p)'' is the set of all vertices that are adjacent to p, and ''C'' its corresponding set of color classes. The MaxClique algorithm recursively searches for a maximum clique by adding and removing vertices to and from ''Q''.

	==Coloring algorithms==		==Coloring algorithms==

178.197.203.0: Add clarification about Γ symbol in MaxClique algorithm, based on the underlying paper: https://web.archive.org/web/20160911054636/http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/tomita2003.pdf

2024-12-23T11:37:51Z

Add clarification about Γ symbol in MaxClique algorithm, based on the underlying paper: https://web.archive.org/web/20160911054636/http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/tomita2003.pdf

← Previous revision		Revision as of 11:37, 23 December 2024
Line 48:		Line 48:
	'''end while'''		'''end while'''

	where ''Q'' is a set of vertices of the currently growing clique, ''Q''<sub>max</sub> is a set of vertices of the largest clique currently found, ''R'' is a set of candidate vertices, and ''C'' its corresponding set of color classes. The MaxClique algorithm recursively searches for a maximum clique by adding and removing vertices to and from ''Q''.		where ''Q'' is a set of vertices of the currently growing clique, ''Q''<sub>max</sub> is a set of vertices of the largest clique currently found, ''R'' is a set of candidate vertices, Γ(p) is the set of all vertices that are adjacent to p, and ''C'' its corresponding set of color classes. The MaxClique algorithm recursively searches for a maximum clique by adding and removing vertices to and from ''Q''.

	==Coloring algorithms==		==Coloring algorithms==

Citation bot: Altered url. URLs might have been anonymized. Add: archive-date, archive-url. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 83/132

2024-10-25T14:54:59Z

Altered url. URLs might have been anonymized. Add: archive-date, archive-url. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Graph algorithms | #UCB_Category 83/132

← Previous revision		Revision as of 14:54, 25 October 2024
Line 29:		Line 29:

	==MaxClique algorithm==		==MaxClique algorithm==
	The MaxClique algorithm<ref name=Tomita2003>{{cite conference \|first1=Etsuji \|last1=Tomita \|first2=Tomokazu \|last2=Seki \|title=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique \|year=2003 \|editor-first1=C. S. \|editor-last1=Calude \|editor-first2=M. J. \|editor-last2=Dinneen \|editor-first3=V. \|editor-last3=Vajnovszki \|book-title=DMTCS 2003 \|series=LNCS \|number=2731 \|pages=278–289 \| url=https://web.archive.org/web/20160911054636/http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/tomita2003.pdf}} See also: {{cite journal \|author1=E. Tomita \|author2=T. Seki \|title=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique \|journal=J Glob Optim \|volume=37 \|pages=95–111 \|year=2007 \|doi=10.1007/s10898-006-9039-7}}</ref> is the basic algorithm from which MaxCliqueDyn is extended. The [[pseudocode]] of the algorithm is:		The MaxClique algorithm<ref name=Tomita2003>{{cite conference \|first1=Etsuji \|last1=Tomita \|first2=Tomokazu \|last2=Seki \|title=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique \|year=2003 \|editor-first1=C. S. \|editor-last1=Calude \|editor-first2=M. J. \|editor-last2=Dinneen \|editor-first3=V. \|editor-last3=Vajnovszki \|book-title=DMTCS 2003 \|series=LNCS \|number=2731 \|pages=278–289 \| url=http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/tomita2003.pdf\|archive-url=https://web.archive.org/web/20160911054636/http://www.dcs.gla.ac.uk/~pat/jchoco/clique/indSetMachrahanish/papers/tomita2003.pdf \|archive-date=2016-09-11 }} See also: {{cite journal \|author1=E. Tomita \|author2=T. Seki \|title=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique \|journal=J Glob Optim \|volume=37 \|pages=95–111 \|year=2007 \|doi=10.1007/s10898-006-9039-7}}</ref> is the basic algorithm from which MaxCliqueDyn is extended. The [[pseudocode]] of the algorithm is:

	'''procedure''' MaxClique(R, C) '''is'''		'''procedure''' MaxClique(R, C) '''is'''

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:09Z

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 148:		Line 148:
	{{Reflist}}		{{Reflist}}

	[[Category:~~Algorithms~~ ~~in graph theory~~]]		[[Category:Graph algorithms]]
	[[Category:Articles with example pseudocode]]		[[Category:Articles with example pseudocode]]

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:22Z

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 148:		Line 148:
	{{Reflist}}		{{Reflist}}

	[[Category:~~Graph~~ ~~algorithms~~]]		[[Category:Algorithms in graph theory]]
	[[Category:Articles with example pseudocode]]		[[Category:Articles with example pseudocode]]

Jayowyn: Copy edits for phrasing, grammar, and math notation cleanup

2023-11-14T19:21:36Z

Copy edits for phrasing, grammar, and math notation cleanup

Show changes

Englaidi at 21:43, 21 October 2023

2023-10-21T21:43:09Z

← Previous revision		Revision as of 21:43, 21 October 2023
Line 23:		Line 23:
	{{multiple issues\|{{copy edit\|date=October 2023}}{{more footnotes needed\|date=October 2023}}}}		{{multiple issues\|{{copy edit\|date=October 2023}}{{more footnotes needed\|date=October 2023}}}}

			The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph.
⚫	~~The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph.~~ It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name=Konc2007>{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.

		⚫	It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name="Konc2007">{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.

	==MaxClique algorithm==		==MaxClique algorithm==

AnomieBOT: Dating maintenance tags: {{Copy edit}} {{More footnotes needed}}

2023-10-13T07:58:57Z

Dating maintenance tags: {{Copy edit}} {{More footnotes needed}}

← Previous revision		Revision as of 07:58, 13 October 2023
Line 21:		Line 21:
	}}		}}

	{{multiple issues\|{{copy edit}}{{more footnotes needed}}}}		{{multiple issues\|{{copy edit\|date=October 2023}}{{more footnotes needed\|date=October 2023}}}}

	The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name=Konc2007>{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.		The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name=Konc2007>{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.

Catttte: {{copy edit}}, {{more footnotes needed}}

2023-10-13T05:58:13Z

{{copy edit}}, {{more footnotes needed}}

← Previous revision		Revision as of 05:58, 13 October 2023
Line 20:		Line 20:
	\| data6 = {{URL\|http://insilab.org/maxclique/}}		\| data6 = {{URL\|http://insilab.org/maxclique/}}
	}}		}}

			{{multiple issues\|{{copy edit}}{{more footnotes needed}}}}

	The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name=Konc2007>{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.		The '''MaxCliqueDyn algorithm''' is an [[algorithm]] for finding a maximum [[Clique problem\|clique]] in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using an improved coloring algorithm. The MaxCliqueDyn extends MaxClique algorithm to include dynamically varying bounds. This algorithm was designed by [[Janez Konc]] and the description was published in 2007. In comparison to earlier algorithms described in the published article <ref name=Konc2007>{{cite journal \|author1=Janez Konc \|author2=Dusanka Janezic \|title=An improved branch and bound algorithm for the maximum clique problem \|journal=MATCH Communications in Mathematical and in Computer Chemistry \|volume=58 \|issue=3 \|pages=569–590 \|year=2007 \| url =http://insilab.org/articles/match2007.pdf}} [http://insilab.org/maxclique Source code]</ref> the MaxCliqueDyn algorithm is improved by an improved approximate coloring algorithm ([[ColorSort algorithm]]) and by applying tighter, more computationally expensive upper bounds on a fraction of the search space. Both improvements reduce time to find maximum clique. In addition to reducing time improved coloring algorithm also reduces the number of steps needed to find a maximum clique.

Catttte: /* MaxClique algorithm */ remove semicolons from pseudocode

2023-10-13T05:54:27Z

MaxClique algorithm: remove semicolons from pseudocode

← Previous revision		Revision as of 05:54, 13 October 2023
Line 27:		Line 27:

	'''procedure''' MaxClique(R, C) '''is'''		'''procedure''' MaxClique(R, C) '''is'''
	Q = Ø; Q<sub>max</sub> = Ø;		Q = Ø, Q<sub>max</sub> = Ø

	'''while''' R ≠ Ø '''do'''		'''while''' R ≠ Ø '''do'''
	choose a vertex p with a maximum color C(p) from set R;		choose a vertex p with a maximum color C(p) from set R
	R := R\{p};		R := R\{p}
	'''if''' \|Q\| + C(p)>\|Q<sub>max</sub>\| '''then'''		'''if''' \|Q\| + C(p)>\|Q<sub>max</sub>\| '''then'''
	Q := Q ⋃ {p};		Q := Q ⋃ {p}
	'''if''' R ⋂ Γ(p) ≠ Ø '''then'''		'''if''' R ⋂ Γ(p) ≠ Ø '''then'''
	obtain a vertex-coloring C' of G(R ⋂ Γ(p));		obtain a vertex-coloring C' of G(R ⋂ Γ(p))
	MaxClique(R ⋂ Γ(p), C');		MaxClique(R ⋂ Γ(p), C')
	'''else if''' \|Q\|>\|Q<sub>max</sub>\| '''then''' Q<sub>max</sub>:=Q;		'''else if''' \|Q\|>\|Q<sub>max</sub>\| '''then''' Q<sub>max</sub> := Q
	Q := Q\{p};		Q := Q\{p}
	'''else'''		'''else'''
	'''return'''		'''return'''