CORAL Seminar: Bernard Gendron, CIRRELT (Director) and DIRO, Université de Montréal

Title: Benders Decomposition, Branch-and-Cut and Hybrid Algorithms for the Minimum Connected Dominating Set Problem

Info about event

Time

Tuesday 27 November 2012,  at 10:00 - 11:00

Location

Fuglesangs Allé 4, 8210 Aarhus V, room 2621(B)-4

Organizer

Sanne Wøhlk

Speaker: Bernard Gendron, CIRRELT (Director) and DIRO, Université de Montréal

Title: Benders Decomposition, Branch-and-Cut and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
(Joint work with:
Abilio Lucena, U. Federal Rio de Janeiro
Alexandre Salles da Cunha, U. Federal Minas Gerais
Luidi Simonetti, U. Federal Fluminense)

Abstract: We present exact algorithms for solving the minimum connected dominating set problem in an undirected graph. The algorithms are based on two approaches: a Benders decomposition algorithm and a branch-and-cut method. We also develop a hybrid algorithm that combines these two approaches. Two variants of each of the three resulting algorithms are considered: a stand-alone version and an iterative probing variant. The latter variant is based on a simple property of the problem, which states that if no connected dominating set of a given cardinality exists, then there are no connected dominating set of lower cardinality. We present computational results on a large set of randomly generated instances.

Organizer: Sanne Wøhlk