Optimal Sink Location Problem for Dynamic Flows in a Tree Network
Summary :
In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1020-1025
- Publication Date
- 2002/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
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
Satoko MAMADA, Kazuhisa MAKINO, Satoru FUJISHIGE, "Optimal Sink Location Problem for Dynamic Flows in a Tree Network" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 1020-1025, May 2002, doi: .
Abstract: In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_1020/_p
Copy
@ARTICLE{e85-a_5_1020,
author={Satoko MAMADA, Kazuhisa MAKINO, Satoru FUJISHIGE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Sink Location Problem for Dynamic Flows in a Tree Network},
year={2002},
volume={E85-A},
number={5},
pages={1020-1025},
abstract={In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Optimal Sink Location Problem for Dynamic Flows in a Tree Network
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1020
EP - 1025
AU - Satoko MAMADA
AU - Kazuhisa MAKINO
AU - Satoru FUJISHIGE
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2002
AB - In this paper we consider a compound problem of dynamic flows and sink location in a tree network. Given a dynamic flow network of tree structure with initial supplies at vertices, the problem is to find a vertex v as a sink in the network such that we can send all the initial suplies to v as quick as possible. This problem can be regarded as a dynamic flow version of the 1-center problem in a tree network. We present an O(n2) time algorithm for the sink location problem, where n is the number of vertices in the network.
ER -
English
