A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique

DOI10.1007/978-3-319-39817-4_21zbMath1475.68253OpenAlexW2487826371MaRDI QIDQ4632188

Atsuki Nagao, Takuro Hatta, Mitsuo Wakatsuki, Hiro Ito, Etsuji Tomita, Kohei Yoshida

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_21

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (2)

On comparing algorithms for the maximum clique problem ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound

Uses Software

• MaxCliqueDyn

Cites Work

• Infra-chromatic bound for exact maximum clique search
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An effective local search for the maximum clique problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Improvements to MCS algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique