%0 Journal Article %1 Östergård2002Fast %A Österg$\backslash$rard, Patric R %D 2002 %J Discret. Appl. Math. %K clique graph weight phd schemdesc %N 1-3 %P 197--207 %R http://dx.doi.org/10.1016/S0166-218X(01)00290-6 %T A fast algorithm for the maximum clique problem %U http://dx.doi.org/10.1016/S0166-218X(01)00290-6 %V 120 %X Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem--which is computationally equivalent to the maximum independent (stable) set problem--is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs.

@article{Östergård2002Fast, abstract = {Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. A branch-and-bound algorithm for the maximum clique problem--which is computationally equivalent to the maximum independent (stable) set problem--is presented with the vertex order taken from a coloring of the vertices and with a new pruning strategy. The algorithm performs successfully for many instances when applied to random graphs and DIMACS benchmark graphs.}, added-at = {2013-12-17T09:48:27.000+0100}, author = {\"{O}sterg$\backslash$rard, Patric R}, biburl = {https://www.bibsonomy.org/bibtex/20f2213e676bcb82d486f7c02c890459e/jullybobble}, doi = {http://dx.doi.org/10.1016/S0166-218X(01)00290-6}, interhash = {f7fb8a66a944b94a0f08a2a2767c38a8}, intrahash = {0f2213e676bcb82d486f7c02c890459e}, journal = {Discret. Appl. Math.}, keywords = {clique graph weight phd schemdesc}, month = aug, number = {1-3}, pages = {197--207}, timestamp = {2014-07-27T15:43:19.000+0200}, title = {{A fast algorithm for the maximum clique problem}}, url = {http://dx.doi.org/10.1016/S0166-218X(01)00290-6}, volume = 120, year = 2002 }