An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph

DOI10.1287/ijoc.2019.0922zbMath1462.05282OpenAlexW3004725848MaRDI QIDQ3386796

Zhuqi Miao, Balabhaskar 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

quasi-cliqueclique relaxationsLagrangian dualitygraph-based data mining

Mathematics Subject Classification ID

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

Related Items (1)

On atomic cliques in temporal graphs

Uses Software

• Gurobi
• SparseMatrix
• MKL
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
• A branch-and-bound approach for maximum quasi-cliques
• An efficient algorithm for solving pseudo clique enumeration problem
• An exact algorithm for the maximum clique problem
• Clustering and domination in perfect graphs
• Complexity of uniqueness and local search in quadratic 0-1 programming
• The maximum clique problem
• A fast algorithm for the maximum clique problem
• A biased random-key genetic algorithm for the maximum quasi-clique problem
• On the maximum quasi-clique problem
• On clique relaxation models in network analysis
• Clique-detection models in computational biochemistry and genomics
• Mining market data: a network approach
• Novel approaches for analyzing biological networks
• The complexity of the matrix eigenproblem
• The university of Florida sparse matrix collection
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• A graph‐theoretic definition of a sociometric clique†
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• A graph‐theoretic generalization of the clique concept
• Nonlinear Programming
• The dense \(k\)-subgraph problem
• Benchmarking optimization software with performance profiles.

This page was built for publication: An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph