On maximum degree-based -quasi-clique problem: complexity and exact approaches

DOI10.1002/NET.21791MaRDI QIDQ4565788zbMATH OpenOpenAlexFDO

Authors Grigory Pastukhov, Alexander Veremyev, Oleg A. Prokopyev, Vladimir Boginski

Publication date 13 June 2018

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.21791

zbMATH Keywords

cliquemixed integer programmingclique relaxationquasi-clique\(k\)-corebranch-and-bounddegree-based quasi-clique

Mathematics Subject Classification ID

Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Recommendations

• On the maximum quasi-clique problem
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• An ellipsoidal bounding scheme for the quasi-clique number of a graph
• LP-based dual bounds for the maximum quasi-clique problem
• A branch-and-bound approach for maximum quasi-cliques

Cited in

(12)

• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs
• On the maximum small-world subgraph problem
• On atomic cliques in temporal graphs
• Hardness and tractability of the \(\gamma\)-complete subgraph problem
• An ellipsoidal bounding scheme for the quasi-clique number of a graph
• On the maximum quasi-clique problem
• An opposition-based memetic algorithm for the maximum quasi-clique problem
• LP-based dual bounds for the maximum quasi-clique problem
• A survey on optimization studies of group centrality metrics
• Preface: Recent advances in telecommunications networks planning and operation
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study

This page was built for publication: On maximum degree-based \(\gamma\)-quasi-clique problem: complexity and exact approaches

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