On maximum degree‐based ‐quasi‐clique problem: Complexity and exact approaches

DOI10.1002/net.21791zbMath1388.05140OpenAlexW2770987319MaRDI QIDQ4565788

Alexander Veremyev, Grigory Pastukhov, Oleg A. Prokopyev, Vladimir L. 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

branch-and-boundmixed integer programmingcliqueclique relaxationquasi-clique\(k\)-coredegree-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)

Related Items (7)

Preface: Recent advances in telecommunications networks planning and operation ⋮ LP-based dual bounds for the maximum quasi-clique problem ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ On atomic cliques in temporal graphs ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ On the maximum small-world subgraph problem

This page was built for publication: On maximum degree‐based ‐quasi‐clique problem: Complexity and exact approaches