Infra-chromatic bound for exact maximum clique search

DOI10.1016/j.cor.2015.06.009zbMath1349.90825OpenAlexW749637598MaRDI QIDQ342100

Pablo San Segundo, Mikhail Batsyn, Alexey Nikolaev

Publication date: 17 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2015.06.009

zbMATH Keywords

combinatorial optimizationbranch-and-boundMaxSATapproximate coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (18)

A new exact maximum clique algorithm for large and massive sparse graphs ⋮ On comparing algorithms for the maximum clique problem ⋮ Reducing hypergraph coloring to clique search ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ The maximum clique interdiction problem ⋮ A new upper bound for the maximum weight clique problem ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ A branch-and-cut algorithm for the edge interdiction clique problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs

Uses Software

• MaxCliqueDyn
• biicode
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact bit-parallel algorithm for the maximum clique problem
• An exact algorithm for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• A fast algorithm for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• An improved bit parallel exact maximum clique algorithm
• Improvements to MCS algorithm for the maximum clique problem
• Clique-detection models in computational biochemistry and genomics
• A review on algorithms for maximum clique problems
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Finding a Maximum Clique in an Arbitrary Graph
• Algorithm 457: finding all cliques of an undirected graph
• Sur le coloriage des graphs

This page was built for publication: Infra-chromatic bound for exact maximum clique search