Multiple cover problem on undirected flow networks

@article{citeulike:1777426, abstract = {Problems concerning the optimum location of various devices installed in transport, communication, and other types of networks relate to the so-called location on network problems. In this paper, we show how an expanded multiple cover problem can be solved in polynomial time for the case of an undirected flow network, which is a special case of the location problem on flow networks. Up to now, such problems were solved in polynomial time for conditions when values of the flow to each vertex were set above a certain constant magnitude. Here, we show the possibility of solving these problems by a simple algorithm even in cases where these magnitudes are different for each vertex. {\copyright} 2000 Scripta Technica, Electron Comm Jpn Pt 3, 84(1): 67-74, 2001}, address = {Department of Information and Electronics Engineering, Niigata Institute of Technology, Kashiwazaki, Japan 945-1195; Faculty of Engineering, Niigata University, Niigata, Japan 950-2181; Faculty of Science and Engineering, Chuo University, Tokyo, Japan 112-8551}, author = {Tamura, Hiroshi and Sugawara, Hidehito and Sengoku, Masakazu and Shinoda, Shoji }, citeulike-article-id = {1777426}, doi = {http://dx.doi.org/10.1002/1520-6440(200101)84:1\%3C67::AID-ECJC7\%3E3.0.CO;2-\%23}, journal = {Electronics and Communications in Japan (Part III: Fundamental Electronic Science)}, keywords = {source\_location}, number = {1}, pages = {67--74}, posted-at = {2007-10-17 03:24:11}, priority = {2}, title = {Multiple cover problem on undirected flow networks}, url = {http://dx.doi.org/10.1002/1520-6440(200101)84:1\%3C67::AID-ECJC7\%3E3.0.CO;2-\%23}, volume = {84}, year = {2001} }

TY - JOUR ID - citeulike:1777426 L3 - citeulike-article-id:1777426 TI - Multiple cover problem on undirected flow networks JF - Electronics and Communications in Japan (Part III: Fundamental Electronic Science) VL - 84 IS - 1 SP - 67 EP - 74 AD - Department of Information and Electronics Engineering, Niigata Institute of Technology, Kashiwazaki, Japan 945-1195; Faculty of Engineering, Niigata University, Niigata, Japan 950-2181; Faculty of Science and Engineering, Chuo University, Tokyo, Japan 112-8551 N2 - Problems concerning the optimum location of various devices installed in transport, communication, and other types of networks relate to the so-called location on network problems. In this paper, we show how an expanded multiple cover problem can be solved in polynomial time for the case of an undirected flow network, which is a special case of the location problem on flow networks. Up to now, such problems were solved in polynomial time for conditions when values of the flow to each vertex were set above a certain constant magnitude. Here, we show the possibility of solving these problems by a simple algorithm even in cases where these magnitudes are different for each vertex. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 84(1): 67-74, 2001 KW - source_location AU - Tamura, Hiroshi AU - Sugawara, Hidehito AU - Sengoku, Masakazu AU - Shinoda, Shoji PY - 2001/// UR - http://dx.doi.org/10.1002/1520-6440(200101)84:1%3C67::AID-ECJC7%3E3.0.CO;2-%23 ER -