{"entities":{"Q1068839":{"pageid":1079591,"ns":120,"title":"Item:Q1068839","lastrevid":66077040,"modified":"2026-04-12T07:22:57Z","type":"item","id":"Q1068839","labels":{"en":{"language":"en","value":"A linear time algorithm for full Steiner trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3931036"}},"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":"Q1068839$AA3EFD61-9FA8-4707-8EFF-0B91F900BD11","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b907851663253d15a26aa06eb3b40f6381d90904","datavalue":{"value":{"text":"A linear time algorithm for full Steiner trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068839$60B0FD61-B8B4-4A5E-9B3A-086FF92B9157","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9382efec656d559e8e9317cfe654acb5c23a7728","datavalue":{"value":"0582.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$59219C2C-3B86-4BBA-8915-32E52C8738D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b62bcda34d3b0ffea73bec70a2a726958727e997","datavalue":{"value":"10.1016/0167-6377(86)90008-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$B5F9F286-2542-4540-B183-6AE2CA0F0A4F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$B1E49096-7743-40BE-B064-1B3FAC4C78FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1068839$9A739EC4-EED2-44A1-850D-502A1A3D6902","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd824ed3d5371def7d568438554f5a771e5acb9d","datavalue":{"value":"Full Steiner trees are building blocks for the construction of Steiner minimal trees. \\textit{Z. A. Melzak} [Can. Math. Bull. 4, 143-148 (1961; Zbl 0101.132)] gave an elegant construction for full Steiner tree. However, no polynomial time implementation of Melzak's construction was previously known. In this paper we show how it can be implemented to run in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068839$0CEA8292-4F96-4988-B4F3-7D8FC539EB9D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$D7574F07-938C-44B3-BC8B-8F1BEA367EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$878C1E5F-7D6B-4AFA-8FC2-AB146ADFE937","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"870d088d7cb1c328f1d2ec044405815c5e8019cf","datavalue":{"value":"3931036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$7910C80D-C2A9-4A14-8B79-537E1E2F5AD0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8b701a110681b15270f6c2469e606c52f6444f2","datavalue":{"value":"Full Steiner trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068839$D1AE99ED-B2B9-4A6B-BD4B-17992EB732FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a182268b8671f8679955cd31639d16e180e5c25f","datavalue":{"value":"Steiner minimal trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068839$B7C52807-B3FC-4292-B141-0569E846097D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ab16d5085e31ce1fc45e44b28bcf421c349d3ff","datavalue":{"value":"Melzak's construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068839$35F3F418-2F06-438E-A552-F262B26EB646","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7925a96980d56bafd4f2e9e4c77ce6cb3fb97c65","datavalue":{"value":{"entity-type":"item","numeric-id":224543,"id":"Q224543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$A5500366-2A5E-4401-B03B-2EC7EE2F2595","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":"Q1068839$FBE571FE-9BD3-4C55-895D-98421D5443A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"14964babd1bf495fa54c6c15b2c117b1dd64c118","datavalue":{"value":"https://doi.org/10.1016/0167-6377(86)90008-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068839$06BA4794-7EA7-4B15-89F6-C7791638A3B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fce57028294efb42cd47f6afccbcb738bd9f6390","datavalue":{"value":"W2021517364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068839$17D5A439-D0A9-4497-BEB0-CC7897CED3B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8aee9e93de8f282a9f0c5bfb307fad089f28360","datavalue":{"value":{"entity-type":"item","numeric-id":4156451,"id":"Q4156451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$CB1F6CAD-4B9B-4AA8-89F6-BB19BC69F452","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83b3561c66a716f852c91d5ccf24af1c42a8e2bd","datavalue":{"value":{"entity-type":"item","numeric-id":5623537,"id":"Q5623537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$DE979A82-88A4-4516-8424-131AB782B414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbb12a609e95759c5e9805181a510f61537795d7","datavalue":{"value":{"entity-type":"item","numeric-id":3329494,"id":"Q3329494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$4B8459C3-93D9-4486-927B-17FA0228039D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a47d1241b02e1d0bbfbf624b5f79557aca4ffd76","datavalue":{"value":{"entity-type":"item","numeric-id":4182533,"id":"Q4182533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$FCE50586-D38A-4E02-AB4E-AEB9B98D8320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fda81e3d0e39c06434c8c6ab9bc988f021f6baca","datavalue":{"value":{"entity-type":"item","numeric-id":5542568,"id":"Q5542568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$C7EDC512-5C5B-42F4-B236-26CF9782A74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f815a6001a60c9b40e3cc96122274c9a3a835ae4","datavalue":{"value":{"entity-type":"item","numeric-id":3283373,"id":"Q3283373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068839$EBCB00CA-D925-4AED-BDD6-F69B39B04A94","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4a68a852ed77b74aafe2cc79f88b9b87ea0a961","datavalue":{"value":{"entity-type":"item","numeric-id":3474661,"id":"Q3474661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f5cd0ad1c53b8f9a2fe2e87b319bfdda546f574","datavalue":{"value":{"amount":"+0.809391975402832","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":"Q1068839$E3134ED6-CA92-4887-9209-EFD22B7E9E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa0412bcc6f69da93743a2db535aa92d48b15ef2","datavalue":{"value":{"entity-type":"item","numeric-id":3082919,"id":"Q3082919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ab767f009d5da9b2f148e698327ad0a257eca9d","datavalue":{"value":{"amount":"+0.8001090884208679","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":"Q1068839$A3339B45-12A3-48D7-8FAE-9D0FA2273D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e95209fa2da84b63922288ab46dd10083fc07b6","datavalue":{"value":{"entity-type":"item","numeric-id":4242783,"id":"Q4242783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c192a5a53f3564c89a3a2c7ebef232f8ea338c13","datavalue":{"value":{"amount":"+0.7977077960968018","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":"Q1068839$B07ACCF8-3229-468D-9F2D-BB7EC9960F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fcff806e74afec2dbc387f97f6e7fb8a317758e","datavalue":{"value":{"entity-type":"item","numeric-id":1076029,"id":"Q1076029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3333e3b509597b161fe359be9045e5783621b4bf","datavalue":{"value":{"amount":"+0.7899221181869507","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":"Q1068839$D9A250C3-965F-459C-97D0-900463C63947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac2a87c2cf230167abafcb762052281f8ad1040c","datavalue":{"value":{"entity-type":"item","numeric-id":911286,"id":"Q911286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37c8fac991e97eb89930b748696d85685cfc6436","datavalue":{"value":{"amount":"+0.7850399017333984","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":"Q1068839$FDDEE5B9-0A4B-4E1F-A268-11A8292B305F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear time algorithm for full Steiner trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear_time_algorithm_for_full_Steiner_trees"}}}}}