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

DOI10.1016/J.DAM.2020.02.003MaRDI QIDQ2664003zbMATH OpenOpenAlexFDO

Authors Fabrizio Marinelli, Andrea Pizzuti, 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

integer reformulationmixed integer programmingquasi-clique

Mathematics Subject Classification ID

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

Recommendations

• On the maximum quasi-clique problem
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• An ellipsoidal bounding scheme for the quasi-clique number of a graph
• A branch-and-bound approach for maximum quasi-cliques
• On maximum degree-based -quasi-clique problem: complexity and exact approaches

Cites work

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

Cited in

(12)

• On the maximum quasi-clique problem
• Near optimal solutions for maximum quasi-bicliques
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Mixed Integer Programming for Searching Maximum Quasi-Bicliques
• An ellipsoidal bounding scheme for the quasi-clique number of a graph
• On maximum degree-based -quasi-clique problem: complexity and exact approaches
• MIP formulations for induced graph optimization problems: a tutorial
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem
• Solving the multiobjective quasi-clique problem
• Ensuring connectedness for the maximum quasi-clique and densest k-subgraph problems
• A branch-and-bound approach for maximum quasi-cliques

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

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