{"entities":{"Q794666":{"pageid":796514,"ns":120,"title":"Item:Q794666","lastrevid":64388733,"modified":"2026-04-11T19:31:35Z","type":"item","id":"Q794666","labels":{"en":{"language":"en","value":"On optimal embeddings of metrics in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3859165"}},"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":"Q794666$6388F809-D682-4603-9C55-70EB07F5F3AE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f8e895d105adc1ac8feb7e9842f2cecad506d57","datavalue":{"value":{"text":"On optimal embeddings of metrics in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794666$492D06E7-2738-49B4-81EC-D69B6A5C8C05","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12b65467f47520845652e1a3c4ded5c7a85d9870","datavalue":{"value":"0541.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$DF0CBFAA-9DF6-47EC-9D85-80146FB94B9D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2ff99b1c20c2b4dfa0b913331bf7a3ed616f179","datavalue":{"value":"10.1016/0095-8956(84)90009-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$AA42859F-4E60-4739-8158-128B2C709311","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10c07f8b7e3cd9f2923ddf5077d5a80431b6d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":201986,"id":"Q201986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$B2223D2C-4059-4E02-B553-76122D09F6CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$6DBC4280-3E2B-437D-8B2A-FDD69463D4BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q794666$009387E5-ECA1-4C90-BBF7-B2E4838DEF9E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b247f8e42c5ceb3236eb228e1f09be711a1fd80","datavalue":{"value":"A graph \\(G=(V,E,w)\\) with vertex set V, edge set E and the weighting function \\(w:\\quad E\\to R^+\\) is said to realize a metric (M,d) if M is a subset of V and if \\(d(a,b)=d_ G(a,b)\\) for all elements a, b of \\(M(d_ G(a,b)\\) denotes the distance between vertices a and b in the graph G). A realization G of (M,d) is called optimal if the sum of all edge lengths of G, denoted w(G) is minimal among all realizations of (M,d). The authors of the paper under review prove first that every finite metric (M,d) has an optimal realization by a graph. Then they investigate cases in which the optimal realization is unique. In a next section there are given examples of optimal realizations. In a fifth section of the paper the authors give a shorter proof of a theorem published first by the author and \\textit{E. Stocki\u012d} [Sibir. Mat. Zh. 13, 558-565 (1972; Zbl 0238.05121)] and give a characterization of tree-realizable metrics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794666$70D276C7-E256-4516-8357-242CA0D02B63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$DEEF1152-D9ED-42A0-BFF7-5B9BE5DB8A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$100C0720-01AE-4417-B10E-ACE8842B6ED8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a7bb3dcffe1b011940d58d9e2582d3505d4a46e","datavalue":{"value":"3859165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$11F4AC39-77A4-49CB-BC9A-F7E106CB264E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c04d61bf968a5b5a43d5c036b2f0ae9fb03a07cb","datavalue":{"value":"graph realizations of distance matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q794666$5A7B1A90-6AF4-45AE-8C82-83370B98E6E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9170bd68d566d4bd88a8d5a7cda1867361e6d42b","datavalue":{"value":"tree realizable metrics","type":"string"},"datatype":"string"},"type":"statement","id":"Q794666$57EE19B7-4F12-40FA-800A-C69E1254C519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0797b6edad347dd87aaf36222a0331967ae17ca","datavalue":{"value":"optimal realization","type":"string"},"datatype":"string"},"type":"statement","id":"Q794666$ABB78F77-B7CD-40EE-B9ED-8D17D7054F4B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f084167e6922b520505fd1e8d0ac3334b96ffbd","datavalue":{"value":{"entity-type":"item","numeric-id":2468028,"id":"Q2468028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$F0A3F5F2-F871-4B56-891E-84164AA9EC20","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":"Q794666$6CADB1D3-71B0-4237-AC6B-CC42557AD9E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1802075d335110d3d248928f119ba0033b965359","datavalue":{"value":"https://doi.org/10.1016/0095-8956(84)90009-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q794666$22922D18-1273-4F9D-BAAF-3E7867E5C185","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b2e5d77d1f0bac90c69a17d900192ec9df95b5f","datavalue":{"value":"W1989964203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794666$B66D0D73-8AC6-4D6C-98F5-03F7AE48BC81","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"65f02593bbb3bbd6623624fa933f613f359afdee","datavalue":{"value":{"entity-type":"item","numeric-id":5553122,"id":"Q5553122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$D699E4F4-EDCF-47D4-A36A-C3452E11C833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"885c0af17638cd451a44f54115261ee06f595123","datavalue":{"value":{"entity-type":"item","numeric-id":1845886,"id":"Q1845886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$0A85BEC9-BD08-41F5-B754-14376198AF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73863c642534bbcb8223172a588659ae286b5e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4750658,"id":"Q4750658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$E30AA97E-5664-4EB4-96CC-79772B3C95D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ceced47d15ff582d7fdb28907a61855b0db6c981","datavalue":{"value":{"entity-type":"item","numeric-id":4182770,"id":"Q4182770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$AFBF27DD-CAD7-4CEF-BF89-0D5190A91AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29b172e4ad045f3155d3b563ba0cf247064f0a90","datavalue":{"value":{"entity-type":"item","numeric-id":5329581,"id":"Q5329581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$97F015D1-728E-41F0-80EE-A426B611E6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d60d2736d71d7326e8600aeab9da0f45b4bfced","datavalue":{"value":{"entity-type":"item","numeric-id":5588444,"id":"Q5588444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$40E984C8-BBF6-45BF-AB6C-1020892A8357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08a0ef1d6cc31a282a8ac63c57abd184518184fd","datavalue":{"value":{"entity-type":"item","numeric-id":3207003,"id":"Q3207003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$A879D04A-D5CE-498D-91B8-7977A07CC415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b791147b894b219125ac2b913d4308204cd60a4","datavalue":{"value":{"entity-type":"item","numeric-id":3320584,"id":"Q3320584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$7DE590D1-E198-45F5-9BCB-F2FF21C14D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2063b6639e878dc6ee22447fd2162d0855939b0c","datavalue":{"value":{"entity-type":"item","numeric-id":5648391,"id":"Q5648391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$C3423E1F-FE8A-46E9-8F7E-BF291A874988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"332294c76c3d2739fb2f2d72fd8fd30cde8d34c5","datavalue":{"value":{"entity-type":"item","numeric-id":3798690,"id":"Q3798690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$98A41623-0D12-4A05-BA02-18B0DB6D38E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b77209382ce10da77f4a2b6c4abbce12af188a5d","datavalue":{"value":{"entity-type":"item","numeric-id":4044592,"id":"Q4044592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$04EE4A4E-9C8D-42B4-B405-1EA6FE932F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be37e082875d25e6b844fc951d974f342af16791","datavalue":{"value":{"entity-type":"item","numeric-id":3902542,"id":"Q3902542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$C9B2E59A-B95F-49D3-86BB-69C316147095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd98c2a60f025b7ae2ec990907c513189b099232","datavalue":{"value":{"entity-type":"item","numeric-id":5567012,"id":"Q5567012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$2C97CFAE-C2A7-4E9F-A50C-C098A748BD28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b0657dd40f4b54968f45e7ee2c1064678d8963","datavalue":{"value":{"entity-type":"item","numeric-id":3320428,"id":"Q3320428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$7247924F-B5BE-47DF-97CF-2057680C7239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cce6031ffc7ea6762c21648fa9b501186a1b0bb","datavalue":{"value":{"entity-type":"item","numeric-id":1163034,"id":"Q1163034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$251996D2-2492-46D1-827D-3D71EC6CEC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba18cdff2ef0f782e0a54e276cbdea8f17e33580","datavalue":{"value":{"entity-type":"item","numeric-id":3947423,"id":"Q3947423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$B59ADCEF-1728-47F7-83A6-F1E0D626A71A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fcaa276979f6620aa85ae510dbef420f7ce30a7","datavalue":{"value":{"entity-type":"item","numeric-id":5530466,"id":"Q5530466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794666$C4C98CAD-B60E-49BE-9415-8931536DAE8A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fbd4cc824996491fbc8676e5b5a64482427b604","datavalue":{"value":{"entity-type":"item","numeric-id":1100481,"id":"Q1100481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"310656219e69c8aea35d1c1d4f1b66cbab86d39c","datavalue":{"value":{"amount":"+0.9092820286750792","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":"Q794666$9C6D6B68-68B3-467D-9C6E-DC560457E1CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f8355a8090ec8044335db9d93d943ff9e101918","datavalue":{"value":{"entity-type":"item","numeric-id":3808120,"id":"Q3808120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb4cfdd1e8fd255094aa7d2600dae0897d0aa053","datavalue":{"value":{"amount":"+0.8879882097244263","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":"Q794666$A73AD4EA-EB1E-413C-A0A3-28D1CB8BED6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0d757d0b20d1306c6308b81bb420634e4261908","datavalue":{"value":{"entity-type":"item","numeric-id":1024315,"id":"Q1024315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"682ec50d45a5eac2dceb1908670597c1d18ea947","datavalue":{"value":{"amount":"+0.8547856211662292","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":"Q794666$B66AEEDE-B08A-484E-ADEF-4325D3C90844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e29e70f7349c96a5a04faae7a04137360c2cb8ea","datavalue":{"value":{"entity-type":"item","numeric-id":6161834,"id":"Q6161834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"822349c697b425c713d6029cad0b0ff8633a2743","datavalue":{"value":{"amount":"+0.8340588212013245","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":"Q794666$C2E077D8-E1AA-498E-8A12-1DE44E8E1542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd6879a467c2db056333b534193fd35cc1de90ba","datavalue":{"value":{"entity-type":"item","numeric-id":2342613,"id":"Q2342613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d95805c5c0769499e1c3e2920c144fbc68d7351c","datavalue":{"value":{"amount":"+0.8280031681060791","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":"Q794666$7DB0C94C-186F-45F1-B7E5-8482FC1D05BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On optimal embeddings of metrics in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_optimal_embeddings_of_metrics_in_graphs"}}}}}