BBMCL

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.


References in zbMATH (referenced in 16 articles , 1 standard article )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Coniglio, Stefano; Furini, Fabio; San Segundo, Pablo: A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts (2021)
  2. Furini, Fabio; Ljubić, Ivana; San Segundo, Pablo; Zhao, Yanlu: A branch-and-cut algorithm for the edge interdiction clique problem (2021)
  3. Mohammadi, Neda; Kadivar, Mehdi: A local core number based algorithm for the maximum clique problem (2021)
  4. Szabó, Sándor: A clique search problem and its application to machine scheduling (2021)
  5. Furini, Fabio; Ljubić, Ivana; Martin, Sébastien; San Segundo, Pablo: The maximum clique interdiction problem (2019)
  6. San Segundo, Pablo; Coniglio, Stefano; Furini, Fabio; Ljubić, Ivana: A new branch-and-bound algorithm for the maximum edge-weighted clique problem (2019)
  7. San Segundo, Pablo; Furini, Fabio; Artieda, Jorge: A new branch-and-bound algorithm for the maximum weighted clique problem (2019)
  8. Corrêa, Ricardo C.; Donne, Diego Delle; Koch, Ivo; Marenco, Javier: General cut-generating procedures for the stable set polytope (2018)
  9. Li, Chu-Min; Liu, Yanli; Jiang, Hua; Manyà, Felip; Li, Yu: A new upper bound for the maximum weight clique problem (2018)
  10. Szabó, Sándor: Estimating clique size by coloring the nodes of auxiliary graphs (2018)
  11. Züge, Alexandre Prusch; Carmo, Renato: On comparing algorithms for the maximum clique problem (2018)
  12. Li, Chu-Min; Jiang, Hua; Manyà, Felip: On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem (2017)
  13. San Segundo, Pablo; Lopez, Alvaro; Artieda, Jorge; Pardalos, Panos M.: A parallel maximum clique algorithm for large and massive sparse graphs (2017)
  14. Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)
  15. San Segundo, Pablo; Lopez, Alvaro; Pardalos, Panos M.: A new exact maximum clique algorithm for large and massive sparse graphs (2016)
  16. San Segundo, Pablo; Tapia, Cristobal: Relaxed approximate coloring in exact maximum clique search (2014)