An ellipsoidal bounding scheme for the quasi-clique number of a graph

DOI10.1287/IJOC.2019.0922MaRDI QIDQ3386796zbMATH OpenOpenAlexFDO

Authors Zhuqi Miao, B. Balasundaram

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.0922

zbMATH Keywords

clique relaxationsgraph-based data miningLagrangian dualityquasi-clique

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• On the maximum quasi-clique problem
• LP-based dual bounds for the maximum quasi-clique problem
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• A branch-and-bound approach for maximum quasi-cliques
• On maximum degree-based -quasi-clique problem: complexity and exact approaches

Cites work

• A biased random-key genetic algorithm for the maximum quasi-clique problem
• A branch-and-bound approach for maximum quasi-cliques
• A fast algorithm for the maximum clique problem
• A graph‐theoretic definition of a sociometric clique†
• A graph‐theoretic generalization of the clique concept
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• An efficient algorithm for solving pseudo clique enumeration problem
• An exact algorithm for the maximum clique problem
• An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
• Benchmarking optimization software with performance profiles.
• Clique relaxations in social network analysis: the maximum k-plex problem
• Clique-detection models in computational biochemistry and genomics
• Clustering and domination in perfect graphs
• Complexity of uniqueness and local search in quadratic 0-1 programming
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Mining market data: a network approach
• Nonlinear Programming
• Novel approaches for analyzing biological networks
• On clique relaxation models in network analysis
• On the maximum quasi-clique problem
• The complexity of the matrix eigenproblem
• The dense \(k\)-subgraph problem
• The maximum clique problem
• The University of Florida sparse matrix collection

Cited in

(8)

• On the maximum quasi-clique problem
• LP-based dual bounds for the maximum quasi-clique problem
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• On maximum degree-based -quasi-clique problem: complexity and exact approaches
• On atomic cliques in temporal graphs
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• Finding conserved low-diameter subgraphs in social and biological networks
• A branch-and-bound approach for maximum quasi-cliques

Describes a project that uses

Uses Software

• MKL
• Gurobi
• SparseMatrix
• DIMACS

This page was built for publication: An ellipsoidal bounding scheme for the quasi-clique number of a graph

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