{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T17:32:03Z","timestamp":1771003923879,"version":"3.50.1"},"reference-count":23,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5276,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, the following location problem is analyzed. Let <jats:italic>N<\/jats:italic> = <jats:italic>(V,E)<\/jats:italic> be an undirected connected simple network, where <jats:italic>V<\/jats:italic> is the vertex set, |<jats:italic>V<\/jats:italic>| = <jats:italic>n<\/jats:italic> and <jats:italic>E<\/jats:italic> is the edge set. There is a nonnegative demand <jats:italic>w<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub> associated with every vertex <jats:italic>u<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub>. It is assumed that every edge <jats:italic>(u<jats:sub>i<\/jats:sub>,u<jats:sub>j<\/jats:sub>)<\/jats:italic> has a probability of failure <jats:italic>p<\/jats:italic><jats:sub><jats:italic>ij<\/jats:italic><\/jats:sub> and that failures can never occur on two edges simultaneously. The problem consists of locating <jats:italic>p<\/jats:italic> facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so\u2010called leaf\u2010tree associated with the network. Third, when <jats:italic>p<\/jats:italic> = 1, the problem is a 1\u2010median problem. When <jats:italic>p<\/jats:italic> &gt; 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when <jats:italic>p<\/jats:italic> &gt; 2, the problem with <jats:italic>p<\/jats:italic> + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with <jats:italic>p<\/jats:italic> facilities. An exact algorithm for this problem is described. It can be executed in either <jats:italic>O<\/jats:italic>(<jats:italic>np<\/jats:italic> + |<jats:italic>E<\/jats:italic>|) time or in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic> + |<jats:italic>E<\/jats:italic>|) time. A numerical example is provided.<\/jats:p>","DOI":"10.1002\/net.3230220303","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:22:23Z","timestamp":1178972543000},"page":"231-246","source":"Crossref","is-referenced-by-count":40,"title":["Location of facilities on a network subject to a single\u2010edge failure"],"prefix":"10.1002","volume":"22","author":[{"given":"Horst A.","family":"Eiselt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Gendreau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilbert","family":"Laporte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"503","volume-title":"Discrete Location Theory","author":"Berman O.","year":"1990"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.4.746"},{"key":"e_1_2_1_4_2","volume-title":"Computer network design problems","author":"Boffey T. B.","year":"1991"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.6.645"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.38.6.1034"},{"key":"e_1_2_1_7_2","volume-title":"Graphs and Networks","author":"Carr\u00e9 B.","year":"1979"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(86)90072-9"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.31.6.764"},{"key":"e_1_2_1_10_2","volume-title":"Location of unreliable facilities","author":"Drezner Z.","year":"1985"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.409"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.5.2.212"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"e_1_2_1_15_2","first-page":"23","volume-title":"Location Decisions: Methodology and Applications","author":"Louvaux F. V.","year":"1986"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90020-3"},{"key":"e_1_2_1_17_2","first-page":"55","volume-title":"Discrete Location Theory","author":"Mirchandani P. B.","year":"1990"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.13.2.85"},{"key":"e_1_2_1_19_2","first-page":"363","article-title":"Locating a broadcast facility in an unreliable network","volume":"28","author":"Nel L. D.","year":"1990","journal-title":"INFOR"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(89)90272-5"},{"key":"e_1_2_1_21_2","first-page":"155","volume-title":"Facility Location Analysis: Theory and Applications","author":"ReVelle C.","year":"1989"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/26.103044"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.17.2.168"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T08:49:50Z","timestamp":1698050990000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1002\/net.3230220303"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220303","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}