[GL14] Network coding and multi-terminal flow problems

Conférence Internationale avec comité de lecture : 3rd International Symposium on Combinatorial Optimization (ISCO), March 2014, pp.42-43, Lisbon, Portugal,
Résumé: Given a telecommunication network with non-negative arc capacities, a special vertex called source, and a set of vertices called terminals, we want to send as much information as possible simultaneously from the source to each terminal. We compare the classical routing scheme modeled by the maximum concurrent flow problem and a network coding approach within a multicast network. Multicast protocols allow an intermediate node to replicate its input data towards several output interfaces, and network coding refers to the ability for an intermediate node to perform coding operations on its inputs (for example, bit-wise XOR or linear combinations) releasing a coded information ow on its outputs. It can be show that the maximum quantity of information that can be routed from the source to each terminal using multicast with network coding is the minimum over all terminals of the value of a maximum flow between the source and the terminal. This means that we compare the maximum concurrent flow with the superposition of independent maximum flows, one for each terminal.

Equipe: oc


@inproceedings {
title="{Network coding and multi-terminal flow problems}",
author=" E. Gourdin and T. Lefebvre ",
booktitle="{ 3rd International Symposium on Combinatorial Optimization (ISCO)}",
address="Lisbon, Portugal",