HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Integral Symmetric 2-Commodity Flows

Aubin Jarry 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Let $G=(V,A)$ be a symmetric digraph, and $\kappa:A\rightarrow\mathbb{N}$ be a symmetric capacity. Let $s_1,s_2,t_1,t_2\in V$ and $v_1,v_2\in\mathbb{N}$. An integral symmetric 2-commodity flow in $G$ from $(s_1,s_2)$ to $(t_1,t_2)$ of value $(v_1,v_2)$ is an integral 4-commodity flow from $(s_1,t_1,s_2,t_2)$ to $(t_1,s_1,t_2,s_2)$ of value $(v_1,v_1,v_2,v_2)$. The Integral Symmetric 2-Commodity Flow Problem consists in finding a symmetric 2-commodity flow $(f_1,f_{-1},$ $f_2,f_{-2})$ from $(s_1,t_1)$ to $(s_2,t_2)$ of value $(v_1,v_2)$ such that $\Sigma f_i\leq\kappa$. It is known that the Integral 2-Commodity Flow Problem is NP-complete for both directed and undirected graphs (\cite{FHW80} and \cite{EIS76}). We prove that the cut criterion is a necessary and sufficient condition for the existence of a solution to the Integral Symmetric 2-Commodity Flow Problem, and give a polynomial-time algorithm in that provides a solution to this problem. The time complexity of our algorithm is \textbf{$6C_{flow}+O(|A|)$}, where $C_{flow}$ is the time complexity of your favorite flow algorithm (usually in $O(|V|\times|A|)$).
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:22:26 PM
Last modification on : Friday, February 4, 2022 - 3:11:35 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:46:35 PM


  • HAL Id : inria-00071963, version 1



Aubin Jarry. Integral Symmetric 2-Commodity Flows. RR-4622, INRIA. 2002. ⟨inria-00071963⟩



Record views


Files downloads