Maximum weight relaxed cliques and Russian doll search revisited

DOI10.1016/j.dam.2016.09.039zbMath1376.05149OpenAlexW2231625113MaRDI QIDQ1686057

Stefan Irnich, Timo Gschwind, Isabel Podlinski

Publication date: 20 December 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.039

zbMATH Keywords

Russian doll searchmaximum weight \(\Pi\) problemoptimal hereditary structuresrelaxed clique

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Scale reduction techniques for computing maximum induced bicliques ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ A GPU based local search algorithm for the unweighted and weighted maximum \(s\)-plex problems ⋮ Continuous cubic formulations for cluster detection problems in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• An exact algorithm for the maximum clique problem
• A fast algorithm for the maximum clique problem
• On clique relaxation models in network analysis
• Node-and edge-deletion NP-complete problems
• Network Analysis

This page was built for publication: Maximum weight relaxed cliques and Russian doll search revisited