Retour aux résultats
Articles (2011), Annals of Operations Research, 188 (1), pp. 307-329

Edge Cover by Connected Bipartite Subgraphs

LIBERTI L., ALFANDARI Laurent , PLATEAU M.-C.

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. Lien vers l'article

LIBERTI, L., ALFANDARI, L. and PLATEAU, M.C. (2011). Edge Cover by Connected Bipartite Subgraphs. Annals of Operations Research, 188(1), pp. 307-329.

Mots clés : #Local-Search, #Bipartite-Graph, #Vertex-Cover, #Constructive-Heuristic, #Edge-Cover