Symmetric 2-commodity Flows donné.

Aubin Jarry
Projet Mascotte


Résumé:

We study integral 2-commodity flows in networks with a special characteristic, namely symmetry. We show that the Symmetric 2-Commodity Flow Problem is in $P$, by proving that the cut criterion is a necessary and sufficient condition for the existence of a solution. We also give a polynomial-time algorithm whose complexity is \textbf{$6C_{flow}+O(|A|)$}, where $C_{flow}$ is the time complexity of your favorite flow algorithm (usually in $O(|V|\times|A|)$). Our result closes an open question in a surprising way, since it is known that the Integral 2-Commodity Flow Problem is NP-complete for both directed and undirected graphs. This work finds application in optical telecommunication networks.

Retour au séminaire