A branch-and-bound approach for maximum quasi-cliques

DOI10.1007/s10479-012-1242-yzbMath1296.90130OpenAlexW2038396396MaRDI QIDQ744705

Foad Mahdavi Pajouh, Zhuqi Miao, Balabhaskar Balasundaram

Publication date: 26 September 2014

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-012-1242-y

zbMATH Keywords

cliquecluster detectionquasi-cliquegraph-based data mining

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (14)

Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Finding maximum subgraphs with relatively large vertex connectivity ⋮ A review on algorithms for maximum clique problems ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ An exact algorithm for the maximum quasi‐clique problem ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Micro-review synthesis for multi-entity summarization ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ Finding clique clusters with the highest betweenness centrality ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ On the maximum small-world subgraph problem

Uses Software

• Pajek
• CPLEX
• Pajek datasets
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for the maximum clique problem
• Clustering and domination in perfect graphs
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• A fast algorithm for the maximum clique problem
• Mining market data: a network approach
• Novel approaches for analyzing biological networks
• E ₁₁ and M theory
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Emergence of Scaling in Random Networks
• A graph‐theoretic definition of a sociometric clique†
• A graph‐theoretic generalization of the clique concept
• Community structure in social and biological networks
• The dense \(k\)-subgraph problem

This page was built for publication: A branch-and-bound approach for maximum quasi-cliques