An improved branch and bound algorithm for the maximum clique problem

zbMATH Open1274.05452MaRDI QIDQ2837833FDOQ2837833

Authors: Janez Konc, Dušanka Janežič 

Publication date: 5 July 2013

Published in: MATCH - Communications in Mathematical and in Computer Chemistry (Search for Journal in Brave)

Recommendations

• An algorithm for finding a maximum clique in a graph
• scientific article; zbMATH DE number 2040957
• A fast algorithm for the maximum clique problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• A simple and faster branch-and-bound algorithm for finding a maximum clique

zbMATH Keywords

algorithmcoloring algorithmdynamically varying boundsfinding a maximum clique

Mathematics Subject Classification ID

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

Cited In (65)

• Title not available (Why is that?)
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• A METHOD FOR COMPUTING UPPER BOUNDS ON THE SIZE OF A MAXIMUM CLIQUE
• Title not available (Why is that?)
• On Bruen chains
• Relaxed approximate coloring in exact maximum clique search
• Coloring the nodes of a directed graph
• Numerical experiments with LP formulations of the maximum clique problem
• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Estimating clique size by coloring the nodes of auxiliary graphs
• On risk-averse maximum weighted subgraph problems
• A New Branch and Bound Algorithm for the Clique Partitioning Problem
• Deciding the confusability of words under tandem repeats in linear time
• A new algorithm for the maximum clique problem
• Optimizing with minimum satisfiability
• Mathematical properties and bounds on haplotyping populations by pure parsimony
• Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
• A branch and bound algorithm for the maximum clique problem
• A local core number based algorithm for the maximum clique problem
• Large-scale mining co-expressed genes in \textit{Arabidopsis} anther: from pair to group
• Parallel maximum clique algorithms with applications to network analysis
• hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
• An exact bit-parallel algorithm for the maximum clique problem
• An improved lower bound related to the Furstenberg-Sárközy theorem
• Coloring the edges of a directed graph
• Note on an improved branch-and-bound algorithm to solve \(n/m/P/F_{\text{max}}\) problems
• Solving the maximum vertex weight clique problem via binary quadratic programming
• Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights
• An adaptive multistart tabu search approach to solve the maximum clique problem
• A fast algorithm for the maximum clique problem
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• A branch and bound algorithm for the maximum clique problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• There is no (75,32,10,16) strongly regular graph
• 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
• A labeling order scheme for the maximum clique problem
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• MaxCliqueDyn
• On comparing algorithms for the maximum clique problem
• Title not available (Why is that?)
• A new exact maximum clique algorithm for large and massive sparse graphs
• Infra-chromatic bound for exact maximum clique search
• An independent set approach for the communication network of the GPS III system
• Principles and Practice of Constraint Programming – CP 2004
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
• Incremental Upper Bound for the Maximum Clique Problem
• A new upper bound for the maximum weight clique problem
• A maximum clique based approximation algorithm for wireless link scheduling under SINR model
• A new table of permutation codes
• A sequential elimination algorithm for computing bounds on the clique number of a graph
• Why is maximum clique often easy in practice?
• A greedy algorithm to construct covering arrays using a graph representation
• A review on algorithms for maximum clique problems
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
• A clique search problem and its application to machine scheduling
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Exact algorithms for maximum clique: a computational study
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• An Algebra for Path Manipulation in Graph Databases
• An improved bit parallel exact maximum clique algorithm
• A parallel maximum clique algorithm for large and massive sparse graphs
• Finding a Maximum Clique in an Arbitrary Graph

This page was built for publication: An improved branch and bound algorithm for the maximum clique problem

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