Continuous cubic formulations for cluster detection problems in networks

DOI10.1007/s10107-020-01572-4zbMath1506.90210OpenAlexW3092908795MaRDI QIDQ2097637

Vladimir Stozhkov, Austin Buchanan, Sergiy I. Butenko, Vladimir L. Boginski

Publication date: 14 November 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-020-01572-4

zbMATH Keywords

clique relaxationsTurán's theoremfractional \(b\)-matchingcubic optimizationmaximum \(s\)-defective clique problemmaximum \(s\)-plex problemMotzkin-Straus formulation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Fast Cluster Detection in Networks by First Order Optimization ⋮ Special issue: Global solution of integer, stochastic and nonconvex optimization problems ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem

Uses Software

• BARON
• Gurobi
• QUALEX
• DIMACS
• QPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Solving the problem of packing equal and unequal circles in a circular container
• Spectral bounds for the clique and independence numbers of graphs
• On standard quadratic optimization problems
• Handbook of test problems in local and global optimization
• Evolution towards the maximum clique
• Efficient algorithms for large scale global optimization: Lennard-Jones clusters
• Frequency-driven tabu search for the maximum \(s\)-plex problem
• Maximum weight relaxed cliques and Russian doll search revisited
• BARON: A general purpose global optimization software package
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• NP-hardness of deciding convexity of quartic polynomials and related problems
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• On clique relaxation models in network analysis
• QPLIB: a library of quadratic programming instances
• A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems
• A new trust region technique for the maximum weight clique problem
• A polyhedral study of the generalized vertex packing problem
• Approximation of the Stability Number of a Graph via Copositive Programming
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• The Co-2-plex Polytope and Integral Systems
• A global optimization approach for solving the maximum clique problem
• A graph‐theoretic generalization of the clique concept
• Continuous Characterizations of the Maximum Clique Problem
• Proofs from THE BOOK
• Solving Quadratic Programming by Cutting Planes
• A new branch-and-bound algorithm for standard quadratic programming problems
• Turan's Graph Theorem
• A General Regularized Continuous Formulation for the Maximum Clique Problem
• New analytical lower bounds on the clique number of a graph
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximum matching and a polyhedron with 0,1-vertices
• Constructing test functions for global optimization using continuous formulations of graph problems
• On copositive programming and standard quadratic optimization problems

This page was built for publication: Continuous cubic formulations for cluster detection problems in networks