{"entities":{"Q1808781":{"pageid":1819523,"ns":120,"title":"Item:Q1808781","lastrevid":69011856,"modified":"2026-04-13T03:43:17Z","type":"item","id":"Q1808781","labels":{"en":{"language":"en","value":"\\(k\\)-Steiner-minimal-trees in metric spaces"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1369775"}},"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":"Q1808781$5046B668-B60D-4C56-89C3-2BBFAE141C2C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"abd5caaa3a2fbbab9ebea7ae9deb50cd7b2284ed","datavalue":{"value":{"text":"\\(k\\)-Steiner-minimal-trees in metric spaces","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1808781$C41A99A9-6A3E-44A1-BB10-5F995CCF7FF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8c60e6b942f55e5e22d54e1f3c45f25cceb52eda","datavalue":{"value":"0935.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$1190ED3B-6BCC-483A-8946-823F5ADB7778","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51d6814d64678893b972ea3346d30a025d62b8f8","datavalue":{"value":"10.1016/S0012-365X(99)00067-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$35DC814A-A927-424F-8746-98C155087B5F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808781$80839486-84E9-4F11-A58F-679CD2246369","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc2df620fd6a8df372731edb4d2b9ffdc4ef3885","datavalue":{"value":{"time":"+2000-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1808781$79DB9E30-5986-4B64-9DB3-068A39686C42","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e843d9d55b6a5b9028c0542f49d26afc6f44a5d3","datavalue":{"value":"For a given set \\(N\\) of points in a metric space, a Steiner-minimal tree (SMT) is a tree, connecting the points of \\(N\\) with minimum total length. A \\(k\\)-SMT is a Steiner tree, but now at most \\(k\\)-additional `Steiner' points (points on the tree with degree at least three that do not belong to \\(N\\)) may be added. The problem to find a 0-SMT is the classic shortest spanning tree problem and can be solved in linear time. On the other hand, the unrestricted Steiner tree problem is NP-hard.   This paper considers the complexity of the \\(k\\)-Steiner tree problem, where \\(k\\) is a given integer (considered to be fixed). It shows that if two conditions are fulfilled, then the problem is polynomial time solvable. The first of these conditions is that there is a natural number \\(c\\) that only depends on the metric space, such that any Steiner point in any \\(k\\)-SMT has vertex degree at most \\(c\\), and the second condition states that for each number \\(n\\) between 3 and \\(kc- k+1\\) there is an algorithm that finds the shortest tree for each set of \\(n\\) points. Also, it is shown that the relative defect going from a \\((k-1)\\)-SMT to a \\(k\\)-SMT tends to zero, when \\(k\\) goes to infinity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$C3C40861-0A32-42BA-844B-3810D008F659","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$83BE0D16-E68C-4B02-8ADE-9946AFA4B786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$1DAFEBB7-6A19-45BF-B037-DF6915CE3DE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"caf7f255366a5340b1b235601e2174600678a41a","datavalue":{"value":"1369775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$01CC19B2-A924-414F-AEC8-65816EA2F18C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20f87686e57cd5798939eefa169b80e212af9083","datavalue":{"value":"metric space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$4C3B3273-6AE8-4E1A-862E-F6E8B2C2FCE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"112ee7cd0aff8a2ca4605b68631f4c1cc65776ea","datavalue":{"value":"Steiner-minimal tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$FB9C029B-40AC-4075-9F6F-42270614F7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a0382610d9d9e28ef95c946357abf690b72349","datavalue":{"value":"Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$4C20376D-816D-4F4B-8BA2-A481CD50233B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22b0628f4c449271f6f90f4fb75f8615965174d5","datavalue":{"value":"spanning tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$33D8713D-E080-4065-9C79-0EC25D31E8AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"432be89fd2cbe9eb9516ea3fd320e735c377cca0","datavalue":{"value":"Steiner point","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$C01DCCDF-188A-4D8B-8EC0-AC2BABB52645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808781$07CCB8F7-91D2-4831-AE7A-A70BE065D11D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e19a8adb2a8db73e878c772ec5946a7d3d820b0e","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808781$F561CB7B-5A14-4131-9832-B2614D55FAAA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808781$703B265F-DE8F-46FB-BBC8-2FCE2EA2FEFD","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":"Q1808781$AAACA908-D4C7-4F35-B865-57072D6B9EE6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a07465c3649b46e19eb6200c02f6c06b2da7c2e","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00067-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1808781$AAF77DA1-5D4E-4A79-82F9-FA86B48E6267","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"deaf191231e79f475f59ccb8c0c33c0eead8d3b1","datavalue":{"value":"W1993673146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808781$55A1864C-4F15-4A49-AC0A-FA9601C7E522","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c965617ac8834e419cdfa6d228c46f8c24db590d","datavalue":{"value":{"entity-type":"item","numeric-id":4234114,"id":"Q4234114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"035678e476bbdb44c13e87aa890fb1a2fb6cfa69","datavalue":{"value":{"amount":"+0.8647438883781433","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":"Q1808781$61C4E173-BDBD-4B8C-9E24-0AF629A81725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecfa9e3cfc4f13d1f11f89c1f7f09861b63f11c7","datavalue":{"value":{"entity-type":"item","numeric-id":4337667,"id":"Q4337667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ce655808133b156622866039ca922d95ac31c6c","datavalue":{"value":{"amount":"+0.852699875831604","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":"Q1808781$FB41550B-DF14-4D9C-9281-E799E6A17D81","rank":"normal"},{"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":"302b01acf6a587a5343fa4b040086c01c247d0c1","datavalue":{"value":{"amount":"+0.8455245494842529","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":"Q1808781$57BAE59A-12DD-4913-8C43-EFE89A929DDC","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":"56219235f205df6a411b3a211e96abeb698eac4a","datavalue":{"value":{"amount":"+0.8441326022148132","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":"Q1808781$BE6DF83D-6776-40F8-BF78-E338EF406746","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(k\\)-Steiner-minimal-trees in metric spaces","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(k%5C)-Steiner-minimal-trees_in_metric_spaces"}}}}}