{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T05:40:39Z","timestamp":1697866839451},"reference-count":17,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7619,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,12]]},"abstract":"Abstract<\/jats:title>The w<\/jats:italic>\u2010centroid problem, denoted by (C<\/jats:italic>), is an optimization problem which has been shown by Kariv and Hakimi to be equivalent, on a tree graph, to the 1\u2010median location problem, denoted by (M). For a general (weighted) connected graph G<\/jats:italic> we develop a duality between (C) (which is defined on G<\/jats:italic>) and a block optimization problem, denoted by (B), and defined over the blocks of G<\/jats:italic>. A block is a maximal nonseparable subgraph. We analyze (B) and (C) by means of two problems equivalent to (B) and (C) respectively, but defined on a blocking graph G<\/jats:bold> which is always a tree. We give an O(\u2223V\u2223) algorithm to solve the two problems on G<\/jats:bold>, and we characterize the solutions. We also show that the solution to a 1\u2010median problem defined on G<\/jats:bold> either solves (M) on the original graph G or localizes the search for a solution to (M) to the vertices of a single block. We introduce an extended version of Goldman's algorithm which (in linear time) either solves (M) on G<\/jats:italic>, or finds the single block of G<\/jats:italic> which contains all solutions to (M).<\/jats:p>","DOI":"10.1002\/net.3230150402","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T20:18:20Z","timestamp":1178914700000},"page":"395-412","source":"Crossref","is-referenced-by-count":14,"title":["Block\u2010vertex duality and the one\u2010median problem"],"prefix":"10.1002","volume":"15","author":[{"given":"M.\u2010L.","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. L.","family":"Francis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. F.","family":"Lawrence","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. J.","family":"Lowe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Tufekci","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","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1976"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90024-4"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.8.4.333"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.24.4.628"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.4.4.406"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.5.2.212"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.6.2.195"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969824"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/B978-1-4832-3187-7.50019-2","volume-title":"Graph Theory and Computing","author":"Rosenstiel P.","year":"1972"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"P. J.Slater Some definitions of central structures. Proceedings of First Southeast Asia Graph Theory Colloquium Singapore 1983 Lecture Notes in Mathematics Springer\u2010Verlag Berlin 1984.","DOI":"10.1007\/BFb0073115"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.29.4.482"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.29.4.498"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1932-1501641-2"},{"key":"e_1_2_1_18_2","unstructured":"B.Zelinka Medians and peripherians of trees. Arch. Math. (Brno) (1968)87\u201395."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T20:06:27Z","timestamp":1697832387000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["10.1002\/net.3230150402"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150402","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}