For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network
Yoshihiro KANEKO Shoji SHINODA Kazuo HORIUCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1992/12/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs, Networks and Matroids
graphs and networks, maximum flow, edge addition, vertex-capacitated, undirected,
Full Text: PDF(738.8KB)>>
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.