On comparing algorithms for the maximum clique problem

DOI10.1016/j.dam.2018.01.005zbMath1394.05127OpenAlexW2791564233MaRDI QIDQ1671301

Renato Carmo, Alexandre Prusch Züge

Publication date: 6 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.01.005

zbMATH Keywords

branch and boundrandom graphsmaximum cliqueexperimental algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

A maximum clique based approximation algorithm for wireless link scheduling under SINR model

Uses Software

• BHOSLIB
• DIMACS
• MaxCliqueDyn
• BBMCL
• BBMCW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infra-chromatic bound for exact maximum clique search
• An exact bit-parallel algorithm for the maximum clique problem
• The worst-case time complexity for generating all maximal cliques and computational experiments
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Refined pivot selection for maximal clique enumeration in graphs
• An exact algorithm for the maximum clique problem
• A fast algorithm for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• Exact algorithms for maximum independent set
• Relaxed approximate coloring in exact maximum clique search
• Open problems around exact algorithms
• Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the probable behaviour of some algorithms for finding the stability number of a graph
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Measure and conquer
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Determining the Stability Number of a Graph
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• An enhanced bitstring encoding for exact maximum clique search in sparse graphs
• Parameterized and Exact Computation
• On cliques in graphs

This page was built for publication: On comparing algorithms for the maximum clique problem