An enhanced bitstring encoding for exact maximum clique search in sparse graphs

DOI10.1080/10556788.2017.1281924zbMATH Open1365.05162OpenAlexW2579912193MaRDI QIDQ5268925FDOQ5268925

Authors: Pablo San Segundo, Jorge Artieda, Mikhail Batsyn, Panos M. Pardalos 

Publication date: 21 June 2017

Published in: Optimization Methods \& Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2017.1281924

Recommendations

• A new exact maximum clique algorithm for large and massive sparse graphs
• An improved bit parallel exact maximum clique algorithm
• A parallel maximum clique algorithm for large and massive sparse graphs
• An exact bit-parallel algorithm for the maximum clique problem
• Fast algorithms for the maximum clique problem on massive sparse graphs

zbMATH Keywords

combinatorial optimizationmaximum cliquebranch-and-boundbitstring

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Relaxed approximate coloring in exact maximum clique search
• Algorithm 457: finding all cliques of an undirected graph
• An exact bit-parallel algorithm for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph
• A review on algorithms for maximum clique problems
• An adaptive multistart tabu search approach to solve the maximum clique problem
• An exact algorithm for the maximum clique problem
• On chromatic number of graphs and set-systems
• An improved bit parallel exact maximum clique algorithm
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Infra-chromatic bound for exact maximum clique search
• A new exact maximum clique algorithm for large and massive sparse graphs
• Fast local search for the maximum independent set problem

Cited In (5)

• The maximum independent union of cliques problem: complexity and exact approaches
• Why Is Maximum Clique Often Easy in Practice?
• On comparing algorithms for the maximum clique problem
• BBMCW
• An improved bit parallel exact maximum clique algorithm

Uses Software

• IncMaxCLQ
• BITSCAN
• PMC

This page was built for publication: An enhanced bitstring encoding for exact maximum clique search in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268925)