A maximum edge-weight clique extraction algorithm based on branch-and-bound
From MaRDI portal
Abstract: The maximum edge-weight clique problem is to find a clique whose sum of edge-weight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been proposed. In this paper, we propose a new exact algorithm based on branch-and-bound. It assigns edge-weights to vertices and calculates upper bounds using vertex coloring. By some computational experiments, we confirmed our algorithm is faster than previous algorithms.
Recommendations
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
- A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
- A new branch-and-bound algorithm for the maximum weighted clique problem
- A fast algorithm for the maximum weight clique problem
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1786225 (Why is no real title available?)
- A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- A branch and bound algorithm for the maximum diversity problem
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- A nonconvex quadratic optimization approach to the maximum edge weight clique problem
- A review on algorithms for maximum clique problems
- A simple and faster branch-and-bound algorithm for finding a maximum clique
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
- An exact algorithm for the maximum clique problem
- An exact bit-parallel algorithm for the maximum clique problem
- Approximating the maximum vertex/edge weighted clique using local search
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
- Error-correcting codes over an alphabet of four elements
- Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
- Greedy and heuristic algorithms for codes and colorings
- Improved infra-chromatic bound for exact maximum clique search
- Mining market data: a network approach
- New facets and a branch-and-cut algorithm for the weighted clique problem.
- On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
- Reducibility among combinatorial problems
- Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report
- Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
Cited in
(7)- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- An extended formulation approach to the edge-weighted maximal clique problem
- A new branch-and-bound algorithm for the maximum weighted clique problem
- A nonconvex quadratic optimization approach to the maximum edge weight clique problem
- Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
- Mathematical programming models and exact algorithms
- A new upper bound for the maximum weight clique problem
This page was built for publication: A maximum edge-weight clique extraction algorithm based on branch-and-bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783045)
