{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T22:58:28Z","timestamp":1770505108579,"version":"3.49.0"},"reference-count":14,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,4,11]],"date-time":"2006-04-11T00:00:00Z","timestamp":1144713600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2006,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article deals with the reverse 1\u2010median problem on graphs with positive vertex weights. The problem is proved to be strongly <jats:italic>N<\/jats:italic><jats:italic>P<\/jats:italic>\u2010hard even in the case of bipartite graphs and not approximable within a constant factor (unless <jats:italic>P<\/jats:italic> = <jats:italic>N<\/jats:italic><jats:italic>P<\/jats:italic>). Furthermore, a linear time algorithm for the reverse 1\u2010median problem on a cycle with linear cost functions (RMC) is developed. It is also shown that there exists an integral optimal solution of RMC if the input data are integral. \u00a9 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 16\u201023 2006<\/jats:p>","DOI":"10.1002\/net.20115","type":"journal-article","created":{"date-parts":[[2006,4,12]],"date-time":"2006-04-12T00:16:49Z","timestamp":1144801009000},"page":"16-23","source":"Crossref","is-referenced-by-count":23,"title":["A linear time algorithm for the reverse 1\u2010median problem on a cycle"],"prefix":"10.1002","volume":"48","author":[{"given":"Rainer E.","family":"Burkard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elisabeth","family":"Gassner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Hatzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,4,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02060467"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240105"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1051\/ro:2001100"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00713-0"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2004.03.003"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008360312607"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00290-9"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1026"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584329"},{"key":"e_1_2_1_11_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038914.26975.9b"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009798010579"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"C.Phillips \u201cThe network inhibition problem \u201dProceedings of the 25th Annual Symposium on the Theory of Computing 1993 pp.776\u2013785.","DOI":"10.1145\/167088.167286"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00122-8"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20115","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T13:24:43Z","timestamp":1697635483000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4,11]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,8]]}},"alternative-id":["10.1002\/net.20115"],"URL":"https:\/\/doi.org\/10.1002\/net.20115","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4,11]]}}}