Journal
INFORMS JOURNAL ON COMPUTING
Volume 33, Issue 3, Pages 1070-1090Publisher
INFORMS
DOI: 10.1287/ijoc.2020.0984
Keywords
graph decomposition; clique relaxations; branch-and-price algorithm; social networks
Categories
Funding
- Google Research Award in Optimization
Ask authors/readers for more resources
The article explores the family of problems related to partitioning and covering graphs with a minimum number of relaxed cliques, with applications in various fields. A unified framework based on branch-and-price techniques is proposed, with new pricing algorithms and branching schemes developed. Comparative studies demonstrate the effectiveness of the framework and the validity of the approach in social network instances.
We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property-for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices-is relaxed. 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, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available