|
|
 |
|
Mardi 1 Juillet
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Branch-and-Price for the relaxed clique Partitioning and Covering Problems |
| Description: |
Roberto Wolfler Calvo Relationships between objects can be modeled with graphs, where nodes
represent the different objects and edges express the relationship.
Social network analysis is an example where clusters, e.g., formed by
members of a community, are studied using cliques and clique
relaxations. A clique is a subgraph with pairwise directly connected
nodes, i.e., a subgraph with diameter one. Several relaxations have been
defined either in terms of distance (k-clique), degree (k-plex, k-core),
diameter (k-club), or density. The majority of the literature deals with
identifying such subgraphs of maximum cardinality or weight. In this
presentation, we consider the generic problem of covering or
partitioning a graph with a set of relaxed cliques. We present an exact
solution fromework for solving the relaxed clique partitioning and
covering problems based on branch-and-price. Herein, the subproblem
consists of finding a relaxed clique of maximum weight. We present
heuristics and a new combinatorial branch-and-bound algorithm for its
resolution.
This is a join work with Fabio Furini and Stefan Irnic. |
|
|
