IEICE TRANSACTIONS on Fundamentals
On a Generalization of a Covering Problem Called Single Cover on Undirected Flow Networks
Summary :
Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.3 pp.544-550
- Publication Date
- 1997/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
- 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
Hiroshi TAMURA, Hidehito SUGAWARA, Masakazu SENGOKU, Shoji SHINODA, "On a Generalization of a Covering Problem Called Single Cover on Undirected Flow Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 3, pp. 544-550, March 1997, doi: .
Abstract: Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_3_544/_p
Copy
@ARTICLE{e80-a_3_544,
author={Hiroshi TAMURA, Hidehito SUGAWARA, Masakazu SENGOKU, Shoji SHINODA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Generalization of a Covering Problem Called Single Cover on Undirected Flow Networks},
year={1997},
volume={E80-A},
number={3},
pages={544-550},
abstract={Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - On a Generalization of a Covering Problem Called Single Cover on Undirected Flow Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 544
EP - 550
AU - Hiroshi TAMURA
AU - Hidehito SUGAWARA
AU - Masakazu SENGOKU
AU - Shoji SHINODA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1997
AB - Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.
ER -
English
