Maximum weight relaxed cliques and Russian Doll Search revisited

作者：Gschwind Timo^*; Irnich Stefan; Podlinski Isabel

来源：Discrete Applied Mathematics, 2018, 234: 131-138.

DOI：10.1016/j.dam.2016.09.039

• Relaxed clique
• Russian Doll Search
• Optimal hereditary structures
• Maximum weight Pi problem

Trukhanov et al. (2013) 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 intensively 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 paper, 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.

• 出版日期2018-1-10