Année
2011
Auteurs
ALFANDARI Laurent, LIBERTI L., PLATEAU M.-C.
Abstract
Le problème étudié consiste à couvrir les arêtes d’un graphe par un nombre minimum de sous-graphes bipartis connexes. Nous montrons que ce problème est NP-difficile, proposons des bornes inférieures via une formulation de type programmation mathématique en nombres entiers, ainsi que plusieurs heuristiques constructives et de recherche locale comparées via des expérimentations numériques.
LIBERTI, L., ALFANDARI, L. et PLATEAU, M.C. (2011). Edge Cover by Connected Bipartite Subgraphs. Annals of Operations Research, 188(1), pp. 307-329.