Soit G=(V,E) un graphe non-orienté et 2-arêtes connexe. Chaque arête et sommet de G est muni d'un poids. Le problème du sous-graphe 2-arêtes connexe de poids minimum dans G (2ECSP), est de trouver un sous-graphe 2-arêtes connexe de G tel que la somme des poids sur ses sommets et ses arête...

Dans cet article nous étudions le problème qui consiste à augmenter au moindre coût le poids de tous les arbres couvrants de poids minimum. Nous considérons le cas où le coût d'augmenter le poids d'une arête du graphe est une fonction linéaire par morceaux, convexe et croissante. Nous...

Le problème d'allocations stables généralise les problèmes d'affectations stables (" one-to-one ", " one-to-many " ou " many-to-many ") à l'attribution de quantités réelles ou d'heures. Il existe deux ensembles d'agents distincts, un ensemble I " employés " et un ensemble J " employeurs...

Dans cet article nous étudions les inégalités de cycles impairs. Nous donnons un nouvel algorithme de séparation de ces inégalités, et nous montrons que lorsque nous ajoutons ces inégalités aux inégalités de la relaxation linéaire nous obtenons le polytope du p-médian dans la classe...