{"entities":{"Q1187352":{"pageid":1198101,"ns":120,"title":"Item:Q1187352","lastrevid":67051899,"modified":"2026-04-12T14:36:33Z","type":"item","id":"Q1187352","labels":{"en":{"language":"en","value":"Steiner tree problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 39208"}},"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":"Q1187352$3EF6E0F7-3046-4946-985C-1FF2068B15E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9abc02230b12ac0e4c483b809aedc52a62183e4","datavalue":{"value":{"text":"Steiner tree problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1187352$D9576F23-AA5C-49FE-BD65-B027C36E14E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"be023c48dff9ad73e1636a0844d9adc21a67e725","datavalue":{"value":"0773.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187352$4C0950BD-C538-4257-99D3-4397358516BE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe338334dac58b9c5abae68ac440e3ffb35af71f","datavalue":{"value":"10.1007/BF01758766","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187352$96658954-C6A3-43E5-9CD7-A665A71DDE7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7ed293495086f7916d5f768db508582dc7c583b","datavalue":{"value":{"entity-type":"item","numeric-id":472410,"id":"Q472410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187352$1DCEBAFB-01B9-4112-98E2-5669A23D75E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81778509c7c34d1a374c80a7a64e0dd6e1cd7f8","datavalue":{"value":{"entity-type":"item","numeric-id":701710,"id":"Q701710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187352$26CAE72C-F826-417A-B695-1B3C8CE60E8B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187352$FB03B84F-2CC2-444C-A4A5-66C063FF5BA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1187352$B8C3C87B-B105-4928-81EC-C2D0FF7DCC19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c86f9e21c9fca3f8cc2a600bf1259e2f38a80a7","datavalue":{"value":"Three problems are introduced. The first problem generalizes the Gilbert- Pollak conjecture in the following way: For a given finite point set \\(P\\) define the ``greedy tree'' \\(\\text{GT}(P)\\) as follows: Start with the points as a forest of 1-node trees; at any stage add the shortest possible line segment to the current forest, which causes two trees to merge; continue until the forest becomes a tree. Conjecture:  \\[ \\inf_ P{\\text{length\\;SMT}(P)\\over\\text{length\\;GT}(P)}=2\\sqrt 3/(2+\\sqrt 3)\\approx 0.92820, \\]  where \\(\\text{SMT}(P)\\) denotes a Steiner Minimal Tree for \\(P\\).   Problem 2 gives an idea to introduce point-equivalences so that finding Steiner Minimal Trees becomes trivial. This implies lower bounds for the length of Steiner Trees in Euclidean \\(d\\)-space.   Problem 3 asks for the relation between the length of a Steiner Minimal Tree and the length of the union of all Steiner Minimal Trees for a given point set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187352$39CA4B90-47FD-48FF-9318-F0B14BA21EEE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187352$78817239-DF3B-4734-B1BF-492D7C058F17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b6549858b16df52559e871287b2b663f3dc12421","datavalue":{"value":"39208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1187352$868B3D5C-C9F9-44CE-B121-DA74EC48F29F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c14bc669f3b9ee77a1a7ce438a17a4d71da7260","datavalue":{"value":"Steiner ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187352$389DF70E-D7D7-4995-8ECC-159609C856B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a713bbc1880175161916ee7aa6491d284dffeb1","datavalue":{"value":"greedy tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187352$46B94DFA-C9A9-4F7E-A694-DD4083A32628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3796506ae4df32612395f65b72685e3996090a45","datavalue":{"value":"Gilbert-Pollak conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187352$279F8716-762F-4429-B595-8588A2235F19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"519a07b46812c155ea4255c90a992b7dbcffa962","datavalue":{"value":"Steiner Minimal Trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1187352$D7972E35-7BE1-46EB-9583-377D5CAB73E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1b54857edcab7426c17c1bfaeb67b1f001fa1741","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1187352$A8807438-A2BE-470D-89C7-B6D07DF3AF01","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":"Q1187352$FC83C363-9A34-45B2-92D7-CC987AD073A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cee2d3fb554cbc59c7ab92fde43b101c81f996e2","datavalue":{"value":{"entity-type":"item","numeric-id":5966604,"id":"Q5966604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d285375351ed6d1a528eb1f7128a18dbec268d7","datavalue":{"value":{"amount":"+1.0000004","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":"Q1187352$FD71D937-FE3F-4209-BF80-CD1206576520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eecfb3330089d464f0075d0b7a4164e59951027","datavalue":{"value":{"entity-type":"item","numeric-id":1202044,"id":"Q1202044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2afc9097496bc69753b720eac734093bc7b223","datavalue":{"value":{"amount":"+0.9786563","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":"Q1187352$0E5C4B4B-73A7-40A0-A697-F1263F5376FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16577368be60d18718e1cb552aaf9d335b6747da","datavalue":{"value":{"entity-type":"item","numeric-id":4400842,"id":"Q4400842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77ee1f163403255e2eed1bf166df4c5c1492eb3f","datavalue":{"value":{"amount":"+0.96241736","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":"Q1187352$F4E51C1B-9793-4687-83A3-88A3D8B2046D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7cc9db39ad2beeaebf5bfdf19cf198e895b77c2","datavalue":{"value":{"entity-type":"item","numeric-id":3760270,"id":"Q3760270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54631f1a2eb33872effdc2e8c212794b4dbd9cd3","datavalue":{"value":{"amount":"+0.94916046","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":"Q1187352$835DE793-C0FE-43A5-92AF-5DB31F17DC18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fadc194b539a10ce1b6553e086f17d17b856f15","datavalue":{"value":{"entity-type":"item","numeric-id":4540078,"id":"Q4540078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22178d3d510aa378710dd2650c383e3b17a8111a","datavalue":{"value":{"amount":"+0.9472507","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":"Q1187352$9405D5CA-C972-47B2-AB2C-1552BF2FECA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c99a6fe9dcae49242cb80ba400b7a109ec7d5c","datavalue":{"value":{"entity-type":"item","numeric-id":3338295,"id":"Q3338295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fdd65757a8270206d0b81e94e56341c6736906b","datavalue":{"value":{"amount":"+0.943177","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":"Q1187352$9C247CB2-E535-4BEA-87AA-274D5EDA001D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d462eea43490b95d3b3dc7a54cd619dd9992defd","datavalue":{"value":{"entity-type":"item","numeric-id":3637313,"id":"Q3637313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de94cbe3e2cf6a1897fccb9ca64df74372258242","datavalue":{"value":{"amount":"+0.9343526","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":"Q1187352$BFC1B67C-4064-4E49-AD3B-26FF0893EC6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15ba60e6f7845fd5c0f25565d381ee101e9ecace","datavalue":{"value":{"entity-type":"item","numeric-id":2434988,"id":"Q2434988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c04c08deb5991796d4d08a6c8fb016dee1a97fa0","datavalue":{"value":{"amount":"+0.9339243","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":"Q1187352$59F00B05-A26B-405F-9E0B-5ADD6CC0421E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a11bb06b121a32605eb25583af54de317f6d8ffa","datavalue":{"value":{"entity-type":"item","numeric-id":1129916,"id":"Q1129916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa483ec468e7af31f1994109f3077996eda73f5c","datavalue":{"value":{"amount":"+0.93362355","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":"Q1187352$060DA197-F06C-44F4-AD22-8E3E0870C665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ec02b899c324d55000ddd03194b0695782b622e","datavalue":{"value":{"entity-type":"item","numeric-id":702772,"id":"Q702772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c98d3dde92a39fb3ae4b0907b69917484415f820","datavalue":{"value":{"amount":"+0.9330487","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":"Q1187352$DF2212C2-E072-4E14-8CA8-FF9CE743E102","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Steiner tree problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Steiner_tree_problems"}}}}}