Integral Symmetric 2-Commodity Flows

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|)$).
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00071963
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:22:26 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:46:35 PM

Identifiers

• HAL Id : inria-00071963, version 1

Citation

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

Record views