Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
MaxCliqueDyn algorithm
open-in-new
<p>The MaxCliqueDyn algorithm is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for finding a maximum <a href="/facts/Clique_problem/cVVBNP08">clique</a> in an undirected graph. </p><p>MaxCliqueDyn is based on the MaxClique algorithm, which finds a maximum clique of bounded size. The bound is found using a <a href="/facts/Coloring_algorithm/J6HoBfP0">coloring algorithm</a>. MaxCliqueDyn extends MaxClique to include dynamically varying bounds. </p><p>This algorithm was designed by Janez Konc and its description was published in 2007. In comparison to earlier algorithms, MaxCliqueDyn has an improved coloring algorithm (ColorSort) and applies 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, the improved coloring algorithm also reduces the number of steps needed to find a maximum clique. </p>