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

Abstract: 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)
Pages: 8 pages
Date: 2015-05-19, Revised 2015-05-19
New Economics Papers: this item is included in nep-cis and nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1504.pdf First version, 2015 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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 ().