An exact bit-parallel algorithm for the maximum clique problem
From MaRDI portal
Publication:709206
DOI10.1016/j.cor.2010.07.019zbMath1231.90369OpenAlexW2068617151MaRDI QIDQ709206
Pablo San Segundo, Agustín Jiménez, Diego Rodriguez-Losada
Publication date: 15 October 2010
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2010.07.019
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)
Related Items (48)
A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations ⋮ Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ A review on algorithms for maximum clique problems ⋮ Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ 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 ⋮ Breakout local search for maximum clique problems ⋮ Infra-chromatic bound for exact maximum clique search ⋮ A new exact maximum clique algorithm for large and massive sparse graphs ⋮ Social structure optimization in team formation ⋮ An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ On finding \(k\)-cliques in \(k\)-partite graphs ⋮ Finding near-optimal independent sets at scale ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ On comparing algorithms for the maximum clique problem ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ A post-quantum associative memory ⋮ Reducing hypergraph coloring to clique search ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ hClique: An exact algorithm for maximum clique problem in uniform hypergraphs ⋮ An improved bit parallel exact maximum clique algorithm ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ A greedy algorithm to construct covering arrays using a graph representation ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ The maximum clique interdiction problem ⋮ Exact algorithms for maximum clique: a computational study ⋮ Multi-threading a state-of-the-art maximum clique algorithm ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs ⋮ General cut-generating procedures for the stable set polytope ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ Recognition of split-graphic sequences ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ Relaxed approximate coloring in exact maximum clique search ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ A branch-and-cut algorithm for the edge interdiction clique problem ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs ⋮ A parallel branch and bound algorithm for the maximum labelled clique problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An exact algorithm for the maximum clique problem
- An algorithm for finding a maximum clique in a graph
- Evolution towards the maximum clique
- A fast algorithm for the maximum clique problem
- A new trust region technique for the maximum weight clique problem
- Clique-detection models in computational biochemistry and genomics
- Continuous Characterizations of the Maximum Clique Problem
- Reducibility among Combinatorial Problems
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Algorithm 457: finding all cliques of an undirected graph
This page was built for publication: An exact bit-parallel algorithm for the maximum clique problem
