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

DOI10.1080/10556788.2017.1281924MaRDI QIDQ5268925zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(6)

• Why is maximum clique often easy in practice?
• A new exact maximum clique algorithm for large and massive sparse graphs
• BBMCW
• The maximum independent union of cliques problem: complexity and exact approaches
• An improved bit parallel exact maximum clique algorithm
• On comparing algorithms for the maximum clique problem

Describes a project that uses

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)