A maximum edge-weight clique extraction algorithm based on branch-and-bound

DOI10.1016/J.DISOPT.2020.100583zbMATH Open1506.90263arXiv1810.10258OpenAlexW3026685272MaRDI QIDQ783045FDOQ783045

Sumio Masuda, Kazuaki Yamaguchi, Satoshi Shimizu

Publication date: 30 July 2020

Published in: Discrete Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1810.10258

zbMATH Keywords

exact algorithmNP-hardbranch-and-boundmaximum edge-weight cliqueupper bound calculation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Mining market data: a network approach
• An exact bit-parallel algorithm for the maximum clique problem
• Approximating the maximum vertex/edge weighted clique using local search
• A review on algorithms for maximum clique problems
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• A branch and bound algorithm for the maximum diversity problem
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
• Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report
• Error-correcting codes over an alphabet of four elements
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• Greedy and heuristic algorithms for codes and colorings
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique

Cited In (3)

• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• Mathematical Programming Models and Exact Algorithms
• An extended formulation approach to the edge-weighted maximal clique problem

Uses Software

• Pajek datasets
• SNAP
• DIMACS

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)