LP-based dual bounds for the maximum quasi-clique problem

DOI10.1016/j.dam.2020.02.003zbMath1464.90083OpenAlexW3010204606MaRDI QIDQ2664003

Andrea Pizzuti, Fabrizio Marinelli, Fabrizio Rossi

Publication date: 20 April 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.02.003

zbMATH Keywords

mixed integer programmingquasi-cliqueinteger reformulation

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

MIP formulations for induced graph optimization problems: a tutorial ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Integer programming formulations for the elementary shortest path problem
• Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
• A branch-and-bound approach for maximum quasi-cliques
• The maximum clique problem
• Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
• On imposing connectivity constraints in integer programs
• On the maximum quasi-clique problem
• On clique relaxation models in network analysis
• The vertex \(k\)-cut problem
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• Decomposition Principle for Linear Programs
• The max quasi-independent set Problem
• On maximum degree‐based ‐quasi‐clique problem: Complexity and exact approaches
• Imposing Connectivity Constraints in Forest Planning Models
• Selected Topics in Column Generation
• Integer models and upper bounds for the 3‐club problem
• The Enumeration of Maximal Cliques of Large Graphs
• Approximation algorithms and hardness results for the clique packing problem
• Benchmarking optimization software with performance profiles.

This page was built for publication: LP-based dual bounds for the maximum quasi-clique problem