An efficient branch-and-bound algorithm for finding a maximum clique

DOI10.1007/3-540-45066-1_22MaRDI QIDQ4452109zbMATH OpenFDO

Authors Etsuji Tomita, Tomokazu Seki

Publication date 11 February 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2731/27310278.htm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• A much faster branch-and-bound algorithm for finding a maximum clique
• An improved branch and bound algorithm for the maximum clique problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• An algorithm for finding a maximum clique in a graph

Cited in

(54)

• An effective local search for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• Detecting robust cliques in graphs subject to uncertain edge failures
• Efficiently enumerating all maximal cliques with bit-parallelism
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• On comparing algorithms for the maximum clique problem
• Multi-threading a state-of-the-art maximum clique algorithm
• Optimizing with minimum satisfiability
• An improved bit parallel exact maximum clique algorithm
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• A clique search problem and its application to machine scheduling
• Numerical experiments with LP formulations of the maximum clique problem
• An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• A greedy algorithm to construct covering arrays using a graph representation
• An effective branch-and-bound algorithm for the maximum s-bundle problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Relaxed approximate coloring in exact maximum clique search
• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Estimating clique size by coloring the nodes of auxiliary graphs
• Coloring the edges of a directed graph
• A parallel branch and bound algorithm for the maximum labelled clique problem
• Improvements to MCS algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• An improved branch and bound algorithm for the maximum clique problem
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• Reducing graph coloring to clique search
• A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• A new exact maximum clique algorithm for large and massive sparse graphs
• A Max-SAT Inference-Based Pre-processing for Max-Clique
• An adaptive multistart tabu search approach to solve the maximum clique problem
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• Finding a Maximum Clique in an Arbitrary Graph
• Coloring the nodes of a directed graph
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Simple and fast: Improving a branch-and-bound algorithm for maximum clique
• scientific article; zbMATH DE number 1560331 (Why is no real title available?)
• hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
• A much faster branch-and-bound algorithm for finding a maximum clique
• Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
• Co-2-plex vertex partitions
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Incremental Upper Bound for the Maximum Clique Problem
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• A parallel maximum clique algorithm for large and massive sparse graphs
• A branch and bound algorithm for the maximum clique problem
• Finding the maximum subgraph of prescribed strength
• Advanced clique algorithms for protein product graphs
• An exact bit-parallel algorithm for the maximum clique problem
• Network portfolio optimization with dynamic lower bounds on asset weights
• PACE solver description: shadoks approach to minimum hitting set and dominating set
• 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

This page was built for publication: An efficient branch-and-bound algorithm for finding a maximum clique

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