{"entities":{"Q1114397":{"pageid":1125146,"ns":120,"title":"Item:Q1114397","lastrevid":49238317,"modified":"2026-01-06T20:11:25Z","type":"item","id":"Q1114397","labels":{"en":{"language":"en","value":"Worst-case performance of Rayward-Smith's Steiner tree heuristic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082970"}},"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":"Q1114397$519D243F-E21A-479A-A9C4-E0629BC0430D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efc0569f2376e8198b326c4bac991caab318117d","datavalue":{"value":{"text":"Worst-case performance of Rayward-Smith's Steiner tree heuristic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114397$773DABD2-8343-4328-BE99-4F3BE399B4A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b198b55572c9fcf4997663ca4b726b115122211d","datavalue":{"value":"0662.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$7AF4A5E5-CA9F-4C1F-BE40-CADE83B6DC78","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eae02a43140a1e54f56dca58292e5783fc81236e","datavalue":{"value":"10.1016/0020-0190(88)90225-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$88FADD81-A50B-4C9E-AC6B-5F5821D4DB44","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc911b17d84f36991204adbef1d8c06cf9c6a1c4","datavalue":{"value":{"entity-type":"item","numeric-id":1114396,"id":"Q1114396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$520E5105-C539-43C7-B408-EBFC5C88C9F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"754f63ae7c58b4d3f5495173b8ab83a0a8e9f92d","datavalue":{"value":{"entity-type":"item","numeric-id":918986,"id":"Q918986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$E3AAAB33-5DB0-45EA-8B0F-6015F3ACBDCA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$5B4CE789-AC9F-4489-8D57-9884AE5B98A5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1114397$69E85FEE-E788-4F61-806C-FA6D36FCF0BC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8bce08b43ba651ff1576d8e8157b6cd139d50f11","datavalue":{"value":"https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1771&context=cse_research","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114397$0AB5828C-8AF4-40CC-AD27-0E3139129314","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e4baa54b73ea04fb6fe142b7b10e55d2374b078","datavalue":{"value":"We prove that the worst-case performance of the Steiner tree approximation algorithm by \\textit{V. J. Rayward-Smith} (RS) [Int. J. Math. Educ. Sci. Technol. 14, 15-23 (1983; Zbl 0512.05024)] is within two times optimal and that two is the best bound in the sense that there are instances for which RS will do worse than any value less than two.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$7BEC118C-0E94-4E0A-8C20-A3FA105BC0F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$C0E4C6F6-7F36-47DD-84DB-ADAE672C4F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$1140C856-BBEA-4747-857F-58D5F09BD7D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$330324C6-0961-4EB0-8976-BA19B9CCC1A1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5e553c4105cb262652d204c4d9c7cf50bcf0ab6","datavalue":{"value":"4082970","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$996A536A-E692-4B72-93CB-5C94C26FB075","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$05606BE2-4DCA-4288-BCDF-AC4EBAB84540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d042f17b2aaf215eddc1e37e7ef0c1f1818cd452","datavalue":{"value":"worst-case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$161450FB-9CD2-4711-90EF-C0D4E1782E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a0382610d9d9e28ef95c946357abf690b72349","datavalue":{"value":"Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$4F338DDE-C4B9-4362-B9C9-A1ED9EAF6600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$0B55CE2E-8C99-4E12-A63C-9078C3BF8970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c66cb78cc5ecae9ecd15324eb4e36a31777b00","datavalue":{"value":"optimal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114397$5C7C0156-876C-430B-A91A-5E68968024B1","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":"Q1114397$41D0DEFE-B126-474C-9991-DC000BC7B043","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"85b5f26dfc98e036ebe27c846ca70f645f884092","datavalue":{"value":"W2087598714","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114397$D6F21F5E-97C9-48F4-B242-07AD66B88C23","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"acd26038edbe6565d3a8583ba4695f74dc5e165b","datavalue":{"value":{"entity-type":"item","numeric-id":4742316,"id":"Q4742316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$C9D922D0-7E91-4A4C-A7CA-6A26686BAB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$B9489DB6-E80E-4CFF-9D59-79B8758C7209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3dcc4318d82c60e62fc117c0c10950118f2ae66","datavalue":{"value":{"entity-type":"item","numeric-id":1145507,"id":"Q1145507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$9898CDFE-5FA0-408B-9A93-5B17728321E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d400d4146bebb1679a82ac4e63c73df4cebb965","datavalue":{"value":{"entity-type":"item","numeric-id":4750659,"id":"Q4750659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$CC6AD0E7-9BCA-4047-AA12-A9E5A2203941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20efe8874389cc4bee4ca1b3db046356ff98bc4c","datavalue":{"value":{"entity-type":"item","numeric-id":3787814,"id":"Q3787814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$A87459CF-AD62-43AC-A57F-943E5818D989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda2b0464290995358834d524225361fb9c7e7fd","datavalue":{"value":{"entity-type":"item","numeric-id":3874241,"id":"Q3874241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$F683D11C-4E90-4DD3-BF1C-CFFBED832D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7761f5a7d78fdf6a95c7409831365b923fe504b6","datavalue":{"value":{"entity-type":"item","numeric-id":3790913,"id":"Q3790913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114397$E1438A5C-EDD5-4D7C-B05E-CE36581DA6A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16f2fd67c7d2f9330b689e62a8758327b4883c70","datavalue":{"value":{"entity-type":"item","numeric-id":3988522,"id":"Q3988522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0717e18044651d452f2719247213dcf96254f435","datavalue":{"value":{"amount":"+0.852687418460846","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":"Q1114397$B6F384C9-EA48-4658-A2BA-39624861C0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfd8237a4b5cb636a3107e4e48b1b239da7d000e","datavalue":{"value":{"entity-type":"item","numeric-id":4028261,"id":"Q4028261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1c31b96201153abb233c09f465a83bbac385a1d","datavalue":{"value":{"amount":"+0.8487673401832581","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":"Q1114397$BD279587-97C3-4594-8CD0-E019F3F9F53F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79698f15575afdb17ec7e6e1347228461e096be7","datavalue":{"value":{"entity-type":"item","numeric-id":4934235,"id":"Q4934235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df8817fe35575bf4b94d7400954f381265890cb5","datavalue":{"value":{"amount":"+0.847457766532898","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":"Q1114397$1EDE642E-22B5-47B2-98A1-B1887FB245FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31e7580e2289808426a9f3f500aa38df676a9a40","datavalue":{"value":{"entity-type":"item","numeric-id":4027188,"id":"Q4027188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8edafb5ace0e39edbc50da10fd9329656c94c6a1","datavalue":{"value":{"amount":"+0.8469878435134888","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":"Q1114397$1835D962-5638-443F-960B-4E90CD995996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb2674fe020c3ac8e66861c7f9e8b0d13c6e0176","datavalue":{"value":{"entity-type":"item","numeric-id":920030,"id":"Q920030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d196305f579ac9d55c950830a3dc3c81bcaf986f","datavalue":{"value":{"amount":"+0.8081717491149902","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":"Q1114397$8401A5CD-B1A9-4F8B-9900-C0A16652D195","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114397","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114397"}}}}}