Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs

DOI10.1007/s10589-015-9804-yzbMath1368.90138OpenAlexW2268749775MaRDI QIDQ276864

Alexander Veremyev, Oleg A. Prokopyev, Eduardo L. Pasiliao, Sergiy I. Butenko

Publication date: 4 May 2016

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-015-9804-y

zbMATH Keywords

mixed integer programming\(s\)-defective cliqueaverage \(s\)-plexclique relaxationdense subgraphquasi-clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Related Items (20)

Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ A biased random-key genetic algorithm for the maximum quasi-clique problem ⋮ Online summarization of dynamic graphs using subjective interestingness for sequential data ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ On atomic cliques in temporal graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ An exact algorithm for the maximum quasi‐clique problem ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ Asymptotic bounds for clustering problems in random graphs ⋮ Mixed Integer Programming for Searching Maximum Quasi-Bicliques ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Dense subgraphs in random graphs ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ On exact solution approaches for the longest induced path problem ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ On the maximum small-world subgraph problem

Uses Software

• Pajek
• Pajek datasets
• SparseMatrix
• XPRESS
• MCODE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Editing graphs into disjoint unions of dense clusters
• A branch-and-bound approach for maximum quasi-cliques
• An efficient algorithm for solving pseudo clique enumeration problem
• Statistical analysis of financial networks
• Integer programming formulation of combinatorial optimization problems
• Classifying molecular sequences using a linkage graph with their pairwise similarities
• The maximum clique problem
• A fast algorithm for the maximum clique problem
• Complexity of finding dense subgraphs
• On the maximum quasi-clique problem
• On clique relaxation models in network analysis
• An integer programming approach for finding the most and the least central cliques
• Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
• Clique-detection models in computational biochemistry and genomics
• Mining market data: a network approach
• Novel approaches for analyzing biological networks
• The university of Florida sparse matrix collection
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• HOW CAN CP VIOLATION IN THE NEUTRINO SECTOR BE LARGE IN A 2 ↔ 3 SYMMETRIC MODEL?
• On the Shannon capacity of a graph
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• The Spectra of Random Graphs with Given Expected Degrees

This page was built for publication: Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs