A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques

Timo Gschwind (), Stefan Irnich (), Fabio Furini and Roberto Wolfler Calvo
Additional contact information
Timo Gschwind: Johannes Gutenberg-Universität Mainz, Germany
Stefan Irnich: Johannes Gutenberg-University Mainz, Germany
Fabio Furini: LAMSADE Université Paris Dauphine, France
Roberto Wolfler Calvo: LIPN Université Paris, France

No 1723, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subset of vertices of a graph for which a clique-defining property is relaxed, e.g., the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new e ective pricing algorithms are developed and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, e.g., structure-preserving versus dichotomous branching and their interplay with di erent pricing algorithms. The finally chosen setup for the branch-and-price produces results that demonstrate the e ectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

Keywords: Graph decomposition; clique relaxations; branch-and-price algorithm; social networks (search for similar items in EconPapers)
Pages: 23 pages
Date: 2017-12-20
New Economics Papers: this item is included in 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_1723.pdf First version, 2017 (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:1723

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