Maximum Weight Relaxed Cliques and Russian Doll Search Revisited
Timo Gschwind (),
Stefan Irnich () and
Isabel Podlinski ()
Additional contact information
Timo Gschwind: Johannes Gutenberg-Universität Mainz, Germany
Stefan Irnich: Johannes Gutenberg-Universität Mainz, Germany
Isabel Podlinski: Zalando SE, Germany
No 1504, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
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.
Keywords: Relaxed clique; Russian Doll Search; Optimal hereditary structures; Maximum weight problem (search for similar items in EconPapers)
New Economics Papers: this item is included in nep-cis and nep-cmp
Date: 2015-05-19, Revised 2015-05-19
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1504.pdf First version, 2015 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1504
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().