{"entities":{"Q460433":{"pageid":462200,"ns":120,"title":"Item:Q460433","lastrevid":52107824,"modified":"2026-01-20T23:07:33Z","type":"item","id":"Q460433","labels":{"en":{"language":"en","value":"The inverse 1-median problem on tree networks with variable real edge lengths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6354643"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$9AE3621B-1040-4AC2-B01A-0EAE5D9C0564","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f25e13409bfb9c18eb03ba72c826482434ff8e5a","datavalue":{"value":{"text":"The inverse 1-median problem on tree networks with variable real edge lengths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q460433$39FAEB0E-7E62-461F-8A1B-932EBB47F1F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c77d562c79e664f1301931b30b524cb49391a8e3","datavalue":{"value":"1296.90131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$A991F988-28F2-485F-A8AA-AA73B4FB338A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"185483f73aa545e3656f32e6374adc9af1d3f485","datavalue":{"value":"10.1155/2013/313868","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$D65E389B-F6EE-4379-91B6-47F9E8A97B19","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1c1ba3ec81099077837c61b4da41d1c1bc1ba6d","datavalue":{"value":{"entity-type":"item","numeric-id":460431,"id":"Q460431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$FE9315D9-90C3-4E8C-8826-90F3DF677692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c961259c12af3527af4f984478a43b0ea3c72d2","datavalue":{"value":{"entity-type":"item","numeric-id":460432,"id":"Q460432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$F3902E8D-66D0-4E68-9AD8-6E4AEE8A1CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5269afad2a7af29aa336aa0961fef960be532e96","datavalue":{"value":{"entity-type":"item","numeric-id":6041194,"id":"Q6041194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$FEE5F40C-F3BF-4A15-8881-C20D00B8B775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7fcd6330711b46fc9088d0d8cfb582c0da0fd29","datavalue":{"value":{"entity-type":"item","numeric-id":6050761,"id":"Q6050761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$4F15DF63-DF64-45D4-9448-87FCD9D66140","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$89695202-1F92-44C5-9BD3-754ED48941C2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0bd9ab9676ef0df75a1a28ac03b07e1906746565","datavalue":{"value":{"time":"+2014-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q460433$9D096C4B-8757-4435-843E-2996240FA059","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f259fa00ca6cca5204127f4919a8b988df71477","datavalue":{"value":"Summary: Location problems exist in the real world and they mainly deal with finding optimal locations for facilities in a network, such as net servers, hospitals, and shopping centers. The inverse location problem is also often met in practice and has been intensively investigated in the literature. As a typical inverse location problem, the inverse 1-median problem on tree networks with variable real edge lengths is discussed in this paper, which is to modify the edge lengths at minimum total cost such that a given vertex becomes a 1-median of the tree network with respect to the new edge lengths. First, this problem is shown to be solvable in linear time with variable nonnegative edge lengths. For the case when negative edge lengths are allowable, the NP-hardness is proved under Hamming distance, and strongly polynomial time algorithms are presented under \\(l_1\\) and \\(l_\\infty\\) norms, respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q460433$AA9E0A00-718E-4271-902C-612E5716E705","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$37A1DC1A-DAD3-47ED-A1F5-0BD43AB4D56E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cea275213fb0787de0302afcc60513543019126f","datavalue":{"value":"6354643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$7001F2EA-5EC8-464B-B3B9-C46D6FD22229","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$73275E4D-BBDC-48D6-B07E-7633F5294101","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d74959b8bae6b7c20da1031c530ccdb7795bb6c","datavalue":{"value":"https://doi.org/10.1155/2013/313868","type":"string"},"datatype":"url"},"type":"statement","id":"Q460433$168C6300-8737-489C-83FC-19856D925D24","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9602d7a03c92230f4c58904c7cb18810f55d47c0","datavalue":{"value":"W1992262116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$3DFF577D-897F-4C46-960C-0826DD8A357D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d967ad6725e913e4836b56f636707916351600d3","datavalue":{"value":"Q59025939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q460433$E723CD46-1487-4B15-8D5D-7666AA63048C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"19ee47c47c223cfb9ec56146022c30ef75f454f0","datavalue":{"value":{"entity-type":"item","numeric-id":3870691,"id":"Q3870691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$915327AC-B37C-4542-92AC-6150868BA6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2616e4f869063ee403af3af762697723c5a513f","datavalue":{"value":{"entity-type":"item","numeric-id":2379654,"id":"Q2379654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$D20DC66F-13DD-4C59-9196-7516034CDA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0617ea13062275a8062a863a3d701a26aea23814","datavalue":{"value":{"entity-type":"item","numeric-id":2482726,"id":"Q2482726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$4C71B5BE-B2BC-443E-ABFA-E10DB55752E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49257f4f8211c16ea7398ee1f8cd30e4a81ac100","datavalue":{"value":{"entity-type":"item","numeric-id":1015317,"id":"Q1015317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$E3577878-5158-40E8-970D-7ACC24A55E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"901b338b0472cd2e5af50066bc2d11d4ddb9dcd1","datavalue":{"value":{"entity-type":"item","numeric-id":764205,"id":"Q764205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$9F09B139-CE0F-4DEA-ABC2-B0E5E57A4309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4571dedcae385bd9f8e94b3efdff2306891d5c4b","datavalue":{"value":{"entity-type":"item","numeric-id":2386211,"id":"Q2386211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$23EDC1B5-218A-41BF-BAEA-9EC365CFE263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"027cbd02f6d499f43cef98ffd12ea88840d3fa55","datavalue":{"value":{"entity-type":"item","numeric-id":951097,"id":"Q951097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$75FAC653-5A0D-470D-A4E8-A3ED4FD2945B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d01b537439cd75d06d48e27fff137cdd554fc88","datavalue":{"value":{"entity-type":"item","numeric-id":976390,"id":"Q976390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$4740D1BD-DEE0-433D-AB0A-7065CAEDA6B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c75eb95e51061bb2551b4c274199288408efb972","datavalue":{"value":{"entity-type":"item","numeric-id":2861561,"id":"Q2861561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$00C0C408-8F0D-436D-B387-0C5A52696DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84070e20e9d78e523cb857767ac61516ed756ceb","datavalue":{"value":{"entity-type":"item","numeric-id":445338,"id":"Q445338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$8BD0F718-54D0-4F81-B5E4-2E62E450C80C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7230153249a6e0f3ea62f3300f6bc26ec5a0457c","datavalue":{"value":{"entity-type":"item","numeric-id":532535,"id":"Q532535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$A64E776E-B3B8-498C-8FC8-47755AEC1A65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$788EC9C8-FA93-4874-A16B-D2607469EAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8558fd9472178d1ba1ac0311a44ebc0dda209469","datavalue":{"value":{"entity-type":"item","numeric-id":1810889,"id":"Q1810889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$7AE03122-F49F-4371-B4C7-07B396C48F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c748c293f9116349c0636ad3af93ce2e522f1bc","datavalue":{"value":{"entity-type":"item","numeric-id":1428068,"id":"Q1428068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$DB781566-5FB7-40AE-9325-26829DE97E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aea04970626c2b6a6205a53b4ddfbe1134bb9c2","datavalue":{"value":{"entity-type":"item","numeric-id":3030579,"id":"Q3030579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$79692F0B-7621-40E2-B5F7-AF32DA53C232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d7440fc6edc5671e6a2729437fe9726c15aab1d","datavalue":{"value":{"entity-type":"item","numeric-id":2385466,"id":"Q2385466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$AD448B01-9567-4BF8-95A1-C01C29586157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b318d0b478e468b986d8d7dbba1b63d27be93beb","datavalue":{"value":{"entity-type":"item","numeric-id":1430275,"id":"Q1430275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q460433$05984D87-83C6-4342-A883-94629C5A56B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"430e87cb015b86a9b34adea8a4cd4aca9052a926","datavalue":{"value":{"entity-type":"item","numeric-id":532535,"id":"Q532535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd859c7a800cb038efb8e498f7e47f909c36ec66","datavalue":{"value":{"amount":"+0.8731897473335266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q460433$C0E84FAC-8489-4D06-A0F4-ACDE190F3919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f58ab52ce9927508f9c31659f0f525e355d4cb4","datavalue":{"value":{"entity-type":"item","numeric-id":2632017,"id":"Q2632017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e03a9529aeffb3bd8baf07f9a1436e64133ac3b7","datavalue":{"value":{"amount":"+0.8450021743774414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q460433$9558F26A-D8F2-437F-BD3A-984C0A736F27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"136d6d2eb1f34797d515e04d60883f77430fe0f9","datavalue":{"value":{"entity-type":"item","numeric-id":4981873,"id":"Q4981873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc69d225f21049da870ccbda9c1ac157a1f88a2","datavalue":{"value":{"amount":"+0.8417403101921082","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q460433$E49AC347-D3CA-4EC8-9B8D-1C66121215B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e61f8a01016b56c088185f8fc89b04b4b23ae06","datavalue":{"value":{"entity-type":"item","numeric-id":3100698,"id":"Q3100698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd2c917e869bd9addb05a5e4fbeb0f0335bc3216","datavalue":{"value":{"amount":"+0.8382096290588379","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q460433$02EDA25E-AF5E-415A-87B7-D2D41667D298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e59d6b2bef5fea33ae4f0917333f01a32e76199b","datavalue":{"value":{"entity-type":"item","numeric-id":2861561,"id":"Q2861561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e2a618cd4a7c600ec56d1d4cde0e835b56c7c52","datavalue":{"value":{"amount":"+0.838157057762146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q460433$585AF7CB-8E04-43B7-9621-3F6AA8C31829","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:460433","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:460433"}}}}}