2022-05-16T23:03:08Zhttps://niigata-u.repo.nii.ac.jp/oaioai:niigata-u.repo.nii.ac.jp:000019092021-03-01T20:50:33ZOn a Generalization of a Covering Problem Called Single Cover on Undirected Flow NetworksOn a Generalization of a Covering Problem Called Single Cover on Undirected Flow NetworksTamura, HiroshiSugawara, HidehitoSengoku, MasakazuShinoda, ShojicopyrightÂ©1997 IEICEgraphs and networksflow networklocation theorycovering problemLocation 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.The Institute of Electronics, Information and Communication Engineers1997-03engjournal articlehttp://hdl.handle.net/10191/6523https://niigata-u.repo.nii.ac.jp/records/1909http://www.ieice.org/jpn/trans_online/AA1082623909168508IEICE transactions on fundamentals of electronics, communications and computer sciencesIEICE transactions on fundamentals of electronics, communications and computer sciencesE80-A3544550https://niigata-u.repo.nii.ac.jp/record/1909/files/e80-a_3_544.pdfapplication/pdf527.9 kB2019-07-29