{"entities":{"Q1015445":{"pageid":1017293,"ns":120,"title":"Item:Q1015445","lastrevid":65957355,"modified":"2026-04-12T06:34:48Z","type":"item","id":"Q1015445","labels":{"en":{"language":"en","value":"The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5552220"}},"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":"Q1015445$E9FE446C-04D6-4270-B79C-1EAC28F91F6F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"534043318072bad9d83630b40b1218599eca19c9","datavalue":{"value":{"text":"The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1015445$1CC180A5-9D70-4A72-9E4B-53E92A84A4A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ddf554ab58e99ab5a1edda2365760bf42842382","datavalue":{"value":"1166.54014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$8AFEE0B4-3C9A-4E74-8029-00D4AE9650D7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2febee684711f4cb1a453192904f1a5144211493","datavalue":{"value":{"entity-type":"item","numeric-id":65457,"id":"Q65457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1015445$B9A87374-C140-4033-BE47-FB67B5D7CE5F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0cec347d54f050ae0dec1dd3bc541b9e6406b282","datavalue":{"value":{"time":"+2009-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1015445$75493064-9276-436B-BE5B-641177AF92B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b60f1ec39b02b568e2554310e92b061a9f0a1ccf","datavalue":{"value":"http://doc.rero.ch/lm.php?url=1000%2C43%2C9%2C20091013165829-WT/Varone_metric_bridge.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1015445$3B080FBE-A5CA-4010-B8AB-9899F95ECD2B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3ffad1b6434634e08986e9504783712259e7daaa","datavalue":{"value":"Let \\(G=(V,E,w)\\) be a graph with vertex and edge sets \\(V\\) and \\(E\\), respectively, and \\(w:E\\rightarrow {\\mathbb{R}}^+\\) a function which assigns a positive weight to each edge of \\(G.\\) Then \\(G\\) is called a realization of a finite metric space \\((M,d),\\) with \\(M=\\{1,\\ldots,n\\}\\) if and only if \\(\\{1,\\ldots,n\\}\\subseteq V\\) and \\(d(i,j)\\) is equal to the length of the shortest chain linking \\(i\\) and \\(j\\) in \\(G,\\) whenever \\(i,j\\in \\{1,\\ldots,n\\}\\). A realization \\(G\\) of \\((M,d)\\) is said optimal if the sum of its weights is minimal among all the realizations of \\((M,d)\\). The Metric Bridge Partition Problem is to determine if the elements of a finite metric space \\((M,d)\\) can be partitioned into two nonempty subsets \\(K\\) and \\(L\\) such that all optimal realizations of \\((M,d)\\) contain a bridge linking \\(K\\) with \\(L\\). The authors prove that this problem is polynomially solvable. They also describe an algorithm that constructs an optimal realization of \\((M,d)\\) from optimal realizations of \\((K,d_{| K})\\) and \\((L,d_{| L})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1015445$4AF2E0C6-E099-4C0F-A8F3-D69646CE082B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9934057d10323980704e6b94db4ebac54a6fd5ff","datavalue":{"value":"54E35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$08FD4A2B-3B26-4A7F-9560-BEC84CCD3BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$EA0E2D31-D271-4275-93CB-136DDE5BA4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$8F0F0008-36AB-4205-8D61-DC950D641599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$7910B7D4-FC11-4484-998D-5497C4D6C3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$DAE0EA20-CD8E-462E-A2C4-6C10023E9D42","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"323416351103ae93d1b2aac380fc114053cae094","datavalue":{"value":"5552220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$67CE485B-C1AE-4014-91F5-573261207ED7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e2c0d369a9b4586e85765c073f183f3d91a27bd","datavalue":{"value":"metric bridge partition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1015445$3136F3C3-7CBF-4077-983F-88674C31E241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00cc557455d8d8fde8b989ad40228e519db5f45d","datavalue":{"value":"realization of finite metric space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1015445$7E030D68-5679-4CC6-A59C-3381F94CC169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0797b6edad347dd87aaf36222a0331967ae17ca","datavalue":{"value":"optimal realization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1015445$F75449E0-A350-4BC6-A415-C046A3D95DD3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1015445$AE5914E3-E54B-499E-B513-99FE79D00C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fadc9689f19b3274ed1c9bcb797f7f882037d1a","datavalue":{"value":{"entity-type":"item","numeric-id":858333,"id":"Q858333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1015445$27B195FA-2927-48DA-B907-DAEFCDFE0007","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b06c1395e4711da17bf8b93bbe80ac88c912a760","datavalue":{"value":{"entity-type":"item","numeric-id":386876,"id":"Q386876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1015445$D072B82B-694E-474A-8BDB-396C0C21B2AD","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":"Q1015445$67653F84-B559-4D53-839C-663BDFF2A23D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f088d4beb2f909b747c3873bac6d34bf6687762","datavalue":{"value":"W2016102556","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$A517BE44-BCD5-4809-9CE5-C902679A633F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f5a388319a468ef0b86a2df06a629ae5e2ff02df","datavalue":{"value":"10.1007/S00357-007-0011-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1015445$F0433C52-D778-4BE2-B456-33D5EEE80835","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1102952412c202658680db4dbab25347aacfb95","datavalue":{"value":{"entity-type":"item","numeric-id":734378,"id":"Q734378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b53c33067b7ec5c545f04b1e99c8ed04f6084466","datavalue":{"value":{"amount":"+0.84301716","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$DC4ACB95-5BED-42CC-9079-8A4B25161CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"559ffc5c655f6c40000b497992488ed2da441edb","datavalue":{"value":{"entity-type":"item","numeric-id":2178736,"id":"Q2178736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb45d880c30c793a8d1d654516fa79020c481193","datavalue":{"value":{"amount":"+0.8406019","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$317597D6-E08C-493C-A46D-D03E2B9BE876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d5da9cb49848800c8f7f658876e1cc6f7f32d25","datavalue":{"value":{"entity-type":"item","numeric-id":4459650,"id":"Q4459650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0c8f0feda5f16e703abf517ad2ea3eeaafc377e","datavalue":{"value":{"amount":"+0.83803993","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$FEF08A6E-808F-4B4F-B6F1-45517DA21988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1327c55ca02652131405f94f6d5654e32cc3cb9","datavalue":{"value":{"entity-type":"item","numeric-id":658028,"id":"Q658028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d30658d7718006dcbd01dab40093a9f2478773f","datavalue":{"value":{"amount":"+0.8361557","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$3132EE09-AC34-453D-A7FC-72BF131BB02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fbecdd89262981ecd6709498044a28052adf2e6","datavalue":{"value":{"entity-type":"item","numeric-id":4924455,"id":"Q4924455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0e3aebd251302f3471af9a3b6bcfb990dd323be","datavalue":{"value":{"amount":"+0.8328772","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$8F3E6AA6-D864-4D8D-8E69-032DEAEE8642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42370415b0bc1cf6a798cdbf7e2037f3c7be3302","datavalue":{"value":{"entity-type":"item","numeric-id":1316923,"id":"Q1316923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de0e31a81b8646da7b4dd78a6cdc1cbc05788f73","datavalue":{"value":{"amount":"+0.82935256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$9FB1542C-9D98-40D5-813C-FE5C2CE3B7DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d8de07e0cbbfbcf667e86d3425a3444b31e8c4e","datavalue":{"value":{"entity-type":"item","numeric-id":5357619,"id":"Q5357619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d769c20f411cc03af0270de321e446ec7aaa4837","datavalue":{"value":{"amount":"+0.8288482","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$72651B66-97F1-4131-A9D4-673ACAE6B4B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffbb34cbaddfd3d56d5917985f9a18024eb0d9b9","datavalue":{"value":{"entity-type":"item","numeric-id":3804485,"id":"Q3804485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70c99b7c38d55933061c47a9fd7628378ae1ea11","datavalue":{"value":{"amount":"+0.821041","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$FF503799-01F4-4E55-B825-F95264E44FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73224c8290ff66ec723192726daa88eab04fd116","datavalue":{"value":{"entity-type":"item","numeric-id":5430423,"id":"Q5430423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77c1a768c611d5c7d713468605a3924692fca9cc","datavalue":{"value":{"amount":"+0.8200797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$AA5F5F8E-BF91-4EBA-BBE9-23EA5374FC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5bda024050c42383f94259aad1b2308753d366","datavalue":{"value":{"entity-type":"item","numeric-id":5501299,"id":"Q5501299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"479ad129d418e990468a2b6a6e9ee2b113814900","datavalue":{"value":{"amount":"+0.8177087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1015445$EDFCD6EA-31B3-4DBF-B2DA-C6D7831641EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_metric_bridge_partition_problem:_Partitioning_of_a_metric_space_into_two_subspaces_linked_by_an_edge_in_any_optimal_realization"}}}}}