A linear programming approach to increasing the weight of all minimum spanning trees

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 formulons ce problème par un programme linéaire et nous donnons un algorithme polynomial pour sa résolution et la résolution du son problème dual.

MoreLess

Year of publication:	2005
Authors:	Baïou, Mourad ; Barahona, Fancisco
Institutions:	HAL

More details

Extent:	application/pdf
Series:	Working Papers.
Type of publication:	Book / Working Paper
Language:	English
Notes:	View the original document on HAL open archive server: http://hal.archives-ouvertes.fr/hal-00242975/en/
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10008793842