×

BBMCL

swMATH ID: 11525
Software Authors: San Segundo, Pablo; Tapia, Cristobal
Description: Relaxed approximate coloring in exact maximum clique search. This paper presents selective coloring as a new paradigm for branch-and-bound exact maximum clique search. Approximate coloring has, in recent, years been at the heart of leading solvers in the field. Selective coloring proposes to relax coloring up to a certain threshold. The result is a less informed but lighter decision heuristic.par Different operators for the remaining uncolored vertices give rise to algorithmic variants integrated in a new BBMCL framework. BBMCL allows for an interesting comparison between approximate coloring and degree-based decision heuristics.par The paper also reports extensive empirical tests. Selective coloring algorithms are fastest for a large subset of the graphs considered.
Homepage: http://www.sciencedirect.com/science/article/pii/S0305054813003134
Keywords: combinatorial optimization; approximate coloring; branch-and-bound; global search
Related Software: MaxCliqueDyn; BBMCSP; DIMACS; CPLEX; Algorithm 457; BITSCAN; MINION; SURF; SIFT; k-Vertex-Cut-Problem; Knapsack; SNAP; BBMCW; BHOSLIB; COIN-OR; biicode; LKH
Cited in: 17 Publications

Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
Relaxed approximate coloring in exact maximum clique search. Zbl 1307.90153
San Segundo, Pablo; Tapia, Cristobal
2014
all top 5

Cited by 27 Authors

9 San Segundo, Pablo
6 Furini, Fabio
3 Ljubić, Ivana
2 Artieda, Jorge
2 Coniglio, Stefano
2 Jiang, Hua
2 Li, Chumin
2 López, Álvaro G.
2 Manyà, Felip
2 Pardalos, Panos M.
2 Szabó, Sándor
1 Carmo, Renato
1 Corrêa, Ricardo Cordeiro
1 Donne, Diego Delle
1 Farasat, Alireza
1 Kadivar, Mehdi
1 Koch, Ivo
1 León, Rafael
1 Li, Yu
1 Liu, Yanli
1 Marenco, Javier L.
1 Martin, Sébastien
1 Mohammadi, Neda
1 Nikolaev, Alexander G.
1 Tapia, Cristobal
1 Zhao, Yanlu
1 Züge, Alexandre Prusch
all top 5

Cited in 7 Serials

6 European Journal of Operational Research
5 Computers & Operations Research
2 Discrete Applied Mathematics
1 Optimization Letters
1 Acta Universitatis Sapientiae. Informatica
1 Transactions on Combinatorics
1 SN Operations Research Forum

Cited in 5 Fields

14 Operations research, mathematical programming (90-XX)
12 Combinatorics (05-XX)
2 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
1 Convex and discrete geometry (52-XX)
1 Computer science (68-XX)

Citations by Year