On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network

Yoshihiro KANEKO  Shoji SHINODA  Kazuo HORIUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.12   pp.1785-1792
Publication Date: 1992/12/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs, Networks and Matroids
Keyword: 
graphs and networks,  maximum flow,  edge addition,  vertex-capacitated,  undirected,  

Full Text: PDF>>
Buy this Article



Summary: 
A vertex-capacitated network is a graph whose edges and vertices have infinite positive capacities and finite positive capacities, respectively. Such a network is a model of a communication system in which capacities of links are much larger than those of stations. This paper considers a problem of realizing a flow-saturation in an undirected vertex-capacitated network by adding the least number of edges. By defining a set of influenced vertex pairs by adding edges, we show the follwing results.(1) It suffices to add the least number of edges to unsaturated vertex pairs for realizing flow-saturation.(2) An associated graph of a flow-unsaturated network defined in this paper gives us a sufficient condition that flow-saturation is realized by adding a single edge.