Impact of a varying capacity on the all pairs 2-route network flows

Given an undirected edge-weighted network in which one edge capacity is allowed to vary, we propose in this paper a polynomial algorithm that needs only two 2-cut-trees computations to provide the all pairs maximum 2-route flow values.

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2009-12, Vol.35, p.59-64
Main Authors: Diallo, Madiagne, Gueye, Serigne, Berthomé, Pascal
Format: Article
Language:English
Subjects:
2-cut-tree
2-route flows
cut-tree
multi-terminal
multiroute flows
parametric flows
sensitivity Analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given an undirected edge-weighted network in which one edge capacity is allowed to vary, we propose in this paper a polynomial algorithm that needs only two 2-cut-trees computations to provide the all pairs maximum 2-route flow values.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2009.11.011