Optimization problems for the maximum k-plex

DOI10.1007/S10559-022-00488-5MaRDI QIDQ2103796zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 9 December 2022

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10559-022-00488-5

zbMATH Keywords

maximum cliquequadratic optimization problemBoolean linear programming problemLagrangian dual boundmaximum \(k\)-plexsuperfluous constraint

Mathematics Subject Classification ID

Quadratic programming (90C20) Programming involving graphs or networks (90C35)

Recommendations

• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Exact Solution of the Quadratic Knapsack Problem
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems

Cites work

• A graph‐theoretic generalization of the clique concept
• A more relaxed model for graph-based data clustering: \(s\)-plex cluster editing
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Functionally redundant constraints for Boolean quadratic-type optimization problems
• New quadratic models for the maximum weighted cut problem
• Nondifferentiable optimization and polynomial problems
• On the maximum quasi-clique problem

Cited in

(4)

• On solving simplified diversified top-\(k\,s\)-plex problem
• Mathematical programming formulations for the collapsed k-core problem
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• An Integer Programming Formulation for the Maximum k-Subset Intersection Problem

Describes a project that uses

Uses Software

• Octave
• GLPK

This page was built for publication: Optimization problems for the maximum \(k\)-plex

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