6533b7d9fe1ef96bd126c35e

RESEARCH PRODUCT

Maximum weight relaxed cliques and Russian Doll Search revisited

Timo GschwindStefan IrnichIsabel Podlinski

subject

CliqueDiscrete mathematics021103 operations researchRelaxed clique Russian Doll Search Optimal hereditary structures Maximum weight problemApplied Mathematics010102 general mathematics0211 other engineering and technologies02 engineering and technology01 natural sciencesVerification procedureCombinatoricsCardinalityExact algorithmBundleDiscrete Mathematics and Combinatorics0101 mathematicsMathematicsNetwork analysis

description

Trukhanov et al. [Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013) Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comp. Opt. and Appl., 56(1), 113–130] used the Russian Doll Search (RDS) principle to effectively find maximum hereditary structures in graphs. Prominent examples of such hereditary structures are cliques and some clique relaxations intensely discussed and studied in network analysis. The effectiveness of the tailored RDS by Trukhanov et al. for s-plex and s-defective clique can be attributed to their cleverly designed incremental verification procedures used to distinguish feasible from infeasible structures. In this short note, we clarify the incompletely presented verification procedure for s-plex and present a new and simpler incremental verification procedure for s-defective cliques with a better worst-case runtime. Furthermore, we develop an incremental verification for s-bundle, giving rise to the first exact algorithm for solving the maximum cardinality and maximum weight s-bundle problems.

yearjournalcountryeditionlanguage
2015-05-19Discrete Applied Mathematics
https://doi.org/10.1016/j.dam.2016.09.039