IEICE TRANSACTIONS on Fundamentals
On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.12 pp.1785-1792
- Publication Date
- 1992/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs, Networks and Matroids
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshihiro KANEKO, Shoji SHINODA, Kazuo HORIUCHI, "On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network" in IEICE TRANSACTIONS on Fundamentals,
vol. E75-A, no. 12, pp. 1785-1792, December 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_12_1785/_p
Copy
@ARTICLE{e75-a_12_1785,
author={Yoshihiro KANEKO, Shoji SHINODA, Kazuo HORIUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network},
year={1992},
volume={E75-A},
number={12},
pages={1785-1792},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - On a Realization of "Flow-Saturation" by Adding Edges in an Undirected Vertex-Capacitated Network
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1785
EP - 1792
AU - Yoshihiro KANEKO
AU - Shoji SHINODA
AU - Kazuo HORIUCHI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1992
AB - 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.
ER -
English
