A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

DOI10.1287/IJOC.2019.0898MaRDI QIDQ3386795zbMATH OpenOpenAlexWikidataFDO

Authors Seyedmohammadhossein Hosseinian, Dalila B. M. M. Fontes, Sergiy Butenko

Publication date 7 January 2021

Published in INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.2019.0898

zbMATH Keywords

analytic upper bound on the clique numbergraph theorymaximum edge weight clique problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• A Lagrangian relaxation approach to the edge-weighted clique problem
• scientific article; zbMATH DE number 26478
• A new upper bound for the maximum weight clique problem
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• A note on the complexity of the maximum edge clique partitioning problem with respect to the clique number
• A cutting-plane approach to the edge-weighted maximal clique problem
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• An exact algorithm for the maximum clique problem

Cites work

• A branch and bound algorithm for the maximum diversity problem
• A cutting-plane approach to the edge-weighted maximal clique problem
• A fast algorithm for the maximum clique problem
• A Lagrangian relaxation approach to the 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 sequential elimination algorithm for computing bounds on the clique number of a graph
• 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 for the maximum clique problem
• An exact bit-parallel algorithm for the maximum clique problem
• An extended formulation approach to the edge-weighted maximal clique problem
• Approximating the maximum vertex/edge weighted clique using local search
• Cliques and clustering: A combinatorial approach
• Energy minimization methods in computer vision and pattern recognition. 4th international workshop, EMMCVPR 2003, Lisbon, Portugal, July 7--9, 2003. Proceedings.
• Exact bounds on the order of the maximum clique of a graph.
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• Hybrid heuristics for the maximum diversity problem
• Improvements to MCS algorithm for the maximum clique problem
• Infra-chromatic bound for exact maximum clique search
• Iterated tabu search for the maximum diversity problem
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• On the Shannon capacity of a graph
• Phased local search for the maximum clique problem
• Reducibility among combinatorial problems
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• Solving the maximum edge-weight clique problem in sparse graphs with compact formulations
• Sur le coloriage des graphs
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• The Eigenvalues of a Graph and Its Chromatic Number
• Upper Bounds on the Order of a Clique of a Graph

Cited in

(7)

• A cutting-plane approach to the edge-weighted maximal clique problem
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• A new family of facet defining inequalities for the maximum edge-weighted clique problem
• Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem
• Exact and heuristic solution approaches for the generalized independent set problem
• A maximum edge-weight clique extraction algorithm based on branch-and-bound

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

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