{"entities":{"Q1330879":{"pageid":1341629,"ns":120,"title":"Item:Q1330879","lastrevid":47264263,"modified":"2026-01-01T04:18:56Z","type":"item","id":"Q1330879","labels":{"en":{"language":"en","value":"On the number of minimal 1-Steiner trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 617322"}},"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":"Q1330879$6A3AE13A-65AF-4FB6-ADBC-F1A54C6FBE02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82c129e16caea4ddb756e606029bd4586f3ac7fb","datavalue":{"value":{"text":"On the number of minimal 1-Steiner trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1330879$450221B5-38F7-4CFE-899A-1AFEAB41BDBC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d5e000f15a92ab4aedc825213ef1e9bb50d1fad","datavalue":{"value":"0802.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$DA766795-78EE-4036-9F79-267235C262DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bdc9b2cade5cabf8f36b2cde54d56fa611a69f7f","datavalue":{"value":"10.1007/BF02574363","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$91B93F43-C4A0-4A22-9A9B-46215BE596B4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c957339beeae6f46596c701e650eab7f54dbbfce","datavalue":{"value":{"entity-type":"item","numeric-id":283880,"id":"Q283880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$0654DA19-1114-4CF9-A527-271C6DF5F226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"657551ab5e3350fb34094bc72937119ae48eaff1","datavalue":{"value":{"entity-type":"item","numeric-id":359754,"id":"Q359754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$B2F60BD5-1D1F-4BB1-BEC9-54B4057EC3A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bfda7cf752b9974023d5ffd99e663abde24d7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1105494,"id":"Q1105494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$F324B2E3-F152-4CD6-B35D-7837347A3A24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$1C53113D-32DE-4E58-9056-F504D3B96D3C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fbc2ac0030a794298a44d66dd84da3932fc8da2c","datavalue":{"value":{"time":"+1994-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1330879$451F88C8-1F36-4146-AEEA-C6940D5C5C10","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a6ea2e924b1bf61df545c9c107f75c923fbb689","datavalue":{"value":"https://eudml.org/doc/131315","type":"string"},"datatype":"url"},"type":"statement","id":"Q1330879$DF633814-02CF-4471-9AEF-46855FA9678C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a4f62c9bc9548126131650d502b93d90af425030","datavalue":{"value":"A minimum 1-Steiner tree is a minimum spanning tree whose set of vertices consists of \\(n\\) given points and exactly one additional point. There is an algorithm for constructing such trees in the plane by \\textit{G. Georgakopoulos} and \\textit{C. H. Papadimitriu} [The 1-Steiner tree problem, J. Algorithms 8, 122-130 (1987; Zbl 0642.68131)], fixing the position of the extra vertex in at most \\(O(n^ 2)\\) combinatorially distinct positions and considering the minimum spanning tree of the \\(n+1\\) points.   The paper shows that the maximum possible number of combinatorially distinct minimum 1-Steiner trees on \\(n\\) given points in the \\(d\\)- dimensional space is \\(O(n^ d(\\log n)^{f(d)})\\), where \\(f(d)= 2d^ 2- d\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330879$6F82FEC6-F7CF-4F71-A8D4-DB6C0419B2D8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$3680BC13-E079-411B-8376-99E31AF392D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$763C5FF0-7981-44F8-9785-6C1B340D68CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$F8CE164A-BE1D-4B28-A7E8-51A21A04332B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$701E2BBA-D567-46F6-A0A1-DB6E6C936744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$1D81623D-CE7B-4FD5-92B0-712692BC0DF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66dd25936dc783d8360877881bc18523f85e691b","datavalue":{"value":"617322","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330879$33DD5E1B-6F17-43D0-8E6F-41BEF9319613","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a182268b8671f8679955cd31639d16e180e5c25f","datavalue":{"value":"Steiner minimal trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330879$83869E74-F6F9-4F37-8B89-1959DD639C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e00b41aec3a3d5e9639576d41772e9b291d1b891","datavalue":{"value":"1-Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330879$1928C7E4-DF9E-4847-A62D-268F9F030C6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"732e1592c53acfd9740f2cb8680bbb91fda5b0af","datavalue":{"value":"minimum spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330879$D715AC99-6BE4-4F53-8E09-8FC4ADFEABDE","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":"Q1330879$CD72C2D8-006C-4932-9B78-C04625EB901D","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":"Q1330879$E9710ACE-20D0-46FC-A95C-57C5B53E25C6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d9a2222fc87e27e8577d83ed307bf062f494e2d","datavalue":{"value":{"entity-type":"item","numeric-id":3783604,"id":"Q3783604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$6112CE25-BF7A-411A-BB89-6D677749E3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cbdc4a2ba4de52a71e9bb1596d2f0946f9ea51","datavalue":{"value":{"entity-type":"item","numeric-id":1199130,"id":"Q1199130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$6C55035B-6010-4D55-8A39-4C8460D10C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"317275409be97a7056fb3f62937ae3f09fc39cc1","datavalue":{"value":{"entity-type":"item","numeric-id":796554,"id":"Q796554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$E26A7288-7112-4EE6-9B75-F9FBEFEB86BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99b91b9422501d9d4dd8566bd8d6cd6b0b5c739","datavalue":{"value":{"entity-type":"item","numeric-id":1570427,"id":"Q1570427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330879$490FB6DB-4E1A-42BA-88B5-6DE8956E59A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"295147cf0110e5ed5cc18aae52896d2c023f2170","datavalue":{"value":{"entity-type":"item","numeric-id":4304363,"id":"Q4304363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4712f07a9b9c0eeeba315a9772fcaeeaf55380","datavalue":{"value":{"amount":"+0.8221108317375183","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":"Q1330879$11189DEA-B337-4991-BA9A-ADBEEC9D19E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57274b780711074931753efb747be87f31736dcd","datavalue":{"value":{"entity-type":"item","numeric-id":3978585,"id":"Q3978585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6885c1235dcc6ec5fff17124a123ba101f8e489e","datavalue":{"value":{"amount":"+0.8199867606163025","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":"Q1330879$01D379CE-A8EC-4225-A9CB-1AE1F423368C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d94644933858bf7047e355dcacebbad9bbe8a115","datavalue":{"value":{"entity-type":"item","numeric-id":1186793,"id":"Q1186793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52210519169c69dd35774ec6bba91d6f02779425","datavalue":{"value":{"amount":"+0.8175780773162842","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":"Q1330879$714595A1-4D9C-4D71-A9D8-BAAD1C8843F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2110eba5a2755c3ba8ea228c31f2274c39812109","datavalue":{"value":{"entity-type":"item","numeric-id":828689,"id":"Q828689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43ee4135e77211fd5612079465c5d9ae72f78247","datavalue":{"value":{"amount":"+0.8155724406242371","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":"Q1330879$641FCC55-F453-49FD-9CAE-A7E57CEAA38F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5601d62b6fb2221ee70fd0b8530da9d09ff7289c","datavalue":{"value":{"entity-type":"item","numeric-id":3783604,"id":"Q3783604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8821b4dfd62bcb4bdac15f18164600900b2eba9","datavalue":{"value":{"amount":"+0.8136911988258362","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":"Q1330879$85404B02-E488-48A6-B59D-622B611FE988","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1330879","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1330879"}}}}}