A new exact maximum clique algorithm for large and massive sparse graphs

DOI10.1016/j.cor.2015.07.013zbMath1349.90824OpenAlexW1442132175MaRDI QIDQ342165

Pablo San Segundo, Panos M. Pardalos, Álvaro G. López

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.07.013

zbMATH Keywords

branch and boundmaximum cliquesparsebitstringmassive

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, An extended formulation for the 1‐wheel inequalities of the stable set polytope, Research trends in combinatorial optimization, CliSAT: a new exact algorithm for hard maximum clique problems, Why Is Maximum Clique Often Easy in Practice?, The maximum clique interdiction problem, A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs, A new upper bound for the maximum weight clique problem, A new branch-and-bound algorithm for the maximum weighted clique problem, A branch-and-cut algorithm for the edge interdiction clique problem, SCCWalk: an efficient local search algorithm and its improvements for maximum 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

• DIMACS
• MaxCliqueDyn
• BBMCL
• BBMCSP
• BITSCAN
• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infra-chromatic bound for exact maximum clique search
• An adaptive multistart tabu search approach to solve the maximum clique problem
• Fast local search for the maximum independent set problem
• An exact bit-parallel algorithm for the maximum clique problem
• An exact algorithm for the maximum clique problem
• A fast algorithm for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• Multi-threading a state-of-the-art maximum clique algorithm
• An improved bit parallel exact maximum clique algorithm
• Relaxed approximate coloring in exact maximum clique search
• Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Finding a Maximum Clique in an Arbitrary Graph
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• On chromatic number of graphs and set-systems
• Algorithm 457: finding all cliques of an undirected graph