Problème de flots avec borne inférieure

[cocci]

Bonjour,

Je traite actuellement un problème qui pourrait se ramener à un problème de flots maximal mais sauf qu'en plus des capacités il y aurait également des bornes inférieures sur les arcs. :we:

A votre avis ce problème est il NP complet?

J'aurais tendance à croire que oui, car il me semble avoir démontré que le problème de partition se réduit polynomialement à ce problème, mais j'ai vu des algorithmes sur internet pour ce problème qui m'ont tout l'air d'être polynomial, donc je fais une erreure quelque part mais je ne sais pas si, il y aurait quelque chose de faux dans ma demonstration de NP-complétude ou si l'algorithme que je perçois comme polynomial ne l'est en fait pas du tout. :hein:

Voici un lien vers un site ou il explique l'algorithme : http://www.gerad.ca/~alainh/Flots-Theorie.pdf

merci à ceux que cette question interessera :+++: