Name
Abstract | ||
|---|---|---|
This paper improves an infra-chromatic bound which is used by the exact branch-and bound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.15388/Informatica.2016.95 | INFORMATICA |
Keywords | Field | DocType |
maximum clique, approximate-colouring, branch-and-bound, combinatorial optimization, exact search, maximum satisfiability | Discrete mathematics,Mathematical optimization,Clique,Chromatic scale,Computer science | Journal |
Volume | Issue | ISSN |
27 | 2 | 0868-4952 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pablo San Segundo | 1 | 212 | 13.79 |
| Alexey Nikolaev | 2 | 7 | 1.79 |
| Mikhail Batsyn | 3 | 86 | 10.02 |
| P. M. Pardalos | 4 | 269 | 45.19 |