A fast algorithm for the maximum weight clique problem

DOI10.1007/BF02243394zbMath0791.68127OpenAlexW9324657MaRDI QIDQ1316588

Luitpold Babel

Publication date: 14 March 1994

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02243394

zbMATH Keywords

exact algorithminteger linear programmaximum clique findingweighted problem

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Solving the maximum vertex weight clique problem via binary quadratic programming ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Breakout local search for maximum clique problems ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ On the minimum number of logical clauses inferred from examples ⋮ On risk-averse maximum weighted subgraph problems ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Safe Lower Bounds for Graph Coloring ⋮ A hybrid iterated local search heuristic for the maximum weight independent set problem ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Approximating the maximum vertex/edge weighted clique using local search ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Cliques and clustering: A combinatorial approach

Uses Software

• TABARIS

Cites Work

• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• Finding maximum cliques in arbitrary and in special graphs
• An exact algorithm for the maximum clique problem
• An exact algorithm for the maximum stable set problem
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Finding a Maximum Clique in an Arbitrary Graph
• An algorithm for the maximum internally stable set in a weighted graph
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Vertex packings: Structural properties and algorithms
• A node covering algorithm
• New methods to color the vertices of a graph
• A branch and bound algorithm for the maximum clique problem

This page was built for publication: A fast algorithm for the maximum weight clique problem