{"entities":{"Q1076029":{"pageid":1086781,"ns":120,"title":"Item:Q1076029","lastrevid":66087282,"modified":"2026-04-12T07:27:53Z","type":"item","id":"Q1076029","labels":{"en":{"language":"en","value":"Exact computation of Steiner minimal trees in the plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3952790"}},"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":"Q1076029$354D56F2-DED1-4362-A0AB-13B694C8AB97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ddbd452e96ab552d9adc02b4e96c2a90ecce7cc0","datavalue":{"value":{"text":"Exact computation of Steiner minimal trees in the plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1076029$DD77E391-C70E-4A39-AD0B-B84AE107C6CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d31b0b98880eee20df1b170172bb1832a4a171fd","datavalue":{"value":"0593.05022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$F07FA635-E8D7-49CF-ACE9-09BB1157AE53","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b0072715e52532ff892e3137123d80ef0c127541","datavalue":{"value":"10.1016/0020-0190(86)90062-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$38B246A8-57BB-4503-A766-9682135BA9AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0cd0839c3e414e2f6fde426465f6a8e2fab7644","datavalue":{"value":{"entity-type":"item","numeric-id":189720,"id":"Q189720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$8EA36EA6-C3CB-45CA-B27E-4C040834F731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9823c653f0feeff039729d06d966a81f84ecb175","datavalue":{"value":{"entity-type":"item","numeric-id":1257381,"id":"Q1257381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$C7524408-D9EE-4D33-9104-9F8680815CAA","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":"Q1076029$CC8D295E-6824-49D0-B520-DCEB6FDAE0F4","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":"Q1076029$B060A428-6C87-4997-AD3A-3CD4FB528032","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4afad1459c4f2033594b26415386f3429e965530","datavalue":{"value":"A Steiner minimal tree for a given set \\(A=\\{a_ 1,...,a_ n\\}\\) of plane points is a tree which interconnects these points and whose total length is minimum. The tree may contain other vertices of the plain besides \\(a_ 1,...,a_ n\\). Several algorithms are known for construction of Steiner minimal trees but all of them are of exponential complexity. The present paper further improves the Winter's approach in such a way that all 17-point problems and most of 30-point problems can be solved in a reasonable time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1076029$9D20D515-0698-4932-B6A6-B9C6FC7B70AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$09927AB9-7FDB-4B12-BA49-78583943865D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3c2a2be2b4389d032db4a06f68dc2373e2a230e0","datavalue":{"value":"05B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$B3DA1F65-A85A-485C-B2D5-44F2B8B4A767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2f9920e258389d79a7ef76ef96a77d2e9cc60267","datavalue":{"value":"05-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$5AE596AF-6987-453D-ABA3-05F4233948DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d6002db38b09551989b20dc9c13a586e7dc82e1","datavalue":{"value":"3952790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$C02B6794-DFE8-408F-8A55-EEC4CA0F5232","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc37cf6bf1a4fd159f089028e999146e64828fa8","datavalue":{"value":"SMT","type":"string"},"datatype":"string"},"type":"statement","id":"Q1076029$0779C826-7586-4833-A572-09BD4BF241B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58ad7f6028d3c74c918a2d13b737dbc9acdb38cb","datavalue":{"value":"Steiner minimal tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1076029$14CF46FD-488F-4929-84FB-FDA5D9165800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbf80f7ee9015daab163fced45ec1deb007f95d4","datavalue":{"value":"plane points","type":"string"},"datatype":"string"},"type":"statement","id":"Q1076029$503680F3-30FC-4E58-8A8B-AEC9731E1958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1076029$6FE59353-A8EC-48FF-BA99-6C58D80C5257","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"56a1ca2701a8ace98397887a83075850e16781d0","datavalue":{"value":{"entity-type":"item","numeric-id":274436,"id":"Q274436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$2794E5B8-E0A4-44F4-BBEE-0DA363B99CAC","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":"Q1076029$D1463B63-A6B7-474E-9C45-5D506088DB4D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8aef64b141215e827c228cd0124d5a876e9b0ab9","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90062-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1076029$2814FA5D-8A5A-4537-9C33-8E4F63C6A2CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac67ab200ad5f43276f6a48659d1de052727eb88","datavalue":{"value":"W2029791926","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1076029$9C31E41A-D1C0-4BBD-9512-3FED119EEC7C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$F2F27ECB-5572-4CA2-946D-842B45881E9F","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":"Q1076029$3B6D8F3B-A082-42AF-86C1-71F3CD14B2AD","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":"Q1076029$4551B7B5-750D-4D46-BB37-9C14F5137C10","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":"Q1076029$8704E430-F1BB-4F02-947D-F76ACF91C3A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7792dc47c5d6da7995f97fd716a2832e592938b","datavalue":{"value":{"entity-type":"item","numeric-id":3910011,"id":"Q3910011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$0C44720E-2B24-40F0-9C00-B879AD59CEBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"170561c6a316d9e4b6e629c0818d6879b79e6f3c","datavalue":{"value":{"entity-type":"item","numeric-id":1961044,"id":"Q1961044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1076029$8B530817-E0BC-4F21-BD1E-DD591771A15D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7778b3e5339185abf5e6b041cbce8d0df46a6aa1","datavalue":{"value":{"entity-type":"item","numeric-id":1186797,"id":"Q1186797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e3cf51437940ce2520a904704e5ac012ae9471f","datavalue":{"value":{"amount":"+0.94762546","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":"Q1076029$61DB7968-AB6A-4B49-AC63-877A1439C23C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08c9905bdca6a8099e77754ce402d7b2dc3a8414","datavalue":{"value":{"entity-type":"item","numeric-id":4945796,"id":"Q4945796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37a618d2983f85220e76a3464ef7d7213b5e32fa","datavalue":{"value":{"amount":"+0.9394913","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":"Q1076029$9D8591FC-9395-42D7-9E83-3E92DE6EBF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3494415334094ebd4631a4a593f5baa7efa74b8c","datavalue":{"value":{"entity-type":"item","numeric-id":2064280,"id":"Q2064280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26e7c195d945f3a862411a89bec09c4627c80371","datavalue":{"value":{"amount":"+0.93422574","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":"Q1076029$ED28D06F-8724-433C-9E70-56FB83375735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6349c8586343dd6576f188e0754477fed9e8d045","datavalue":{"value":{"entity-type":"item","numeric-id":1802220,"id":"Q1802220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f25dc52aa4f12be4b53ccdae951e28d6f195171","datavalue":{"value":{"amount":"+0.9322124","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":"Q1076029$256056C9-C679-463B-B425-523687F605CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c19a3ce692d8e2cc9edf25b308fd7e5b29c364f","datavalue":{"value":{"entity-type":"item","numeric-id":4264560,"id":"Q4264560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7749ab6c9c0c7aa69386dfd7f5f4f03f7684ff2","datavalue":{"value":{"amount":"+0.93198633","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":"Q1076029$7651D485-8D56-4821-A92C-4ED2817E3223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5c0f08ef852791a5d7b565fbf503d686ffade1b","datavalue":{"value":{"entity-type":"item","numeric-id":3064040,"id":"Q3064040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11b5001315076e34f5189ddf63cd9a92d320c883","datavalue":{"value":{"amount":"+0.9294045","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":"Q1076029$D7CF20F8-811B-473E-8637-1E7D9C03EA37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2b8a2cc0a9e28c3e88b771b1585b2003daf7c2","datavalue":{"value":{"entity-type":"item","numeric-id":4247448,"id":"Q4247448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aca70a9071f370bd3ed9f2f864dce6cdd872453","datavalue":{"value":{"amount":"+0.9257371","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":"Q1076029$8059CA71-C047-41AE-8CCB-61E8405EA7F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"102df9fe1a4c6f942da2442242f55c58599d73b5","datavalue":{"value":{"entity-type":"item","numeric-id":3970808,"id":"Q3970808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6445815355f10ed28e3a6902aecbae9ef9785ac5","datavalue":{"value":{"amount":"+0.92514277","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":"Q1076029$A8BD5C59-3899-4CCE-B433-299B25F5FBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fd928142c8d1e1187009602a256b7c2b19a8432","datavalue":{"value":{"entity-type":"item","numeric-id":3484850,"id":"Q3484850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b14392c2ff17f94213bf1c7b0b175f7b6b7e9c19","datavalue":{"value":{"amount":"+0.92428386","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":"Q1076029$72E85F26-26BB-48FA-8FE6-151C9C8801E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7b9811d4e7992f131269c7dc1a1ffb1919b3af","datavalue":{"value":{"entity-type":"item","numeric-id":5958113,"id":"Q5958113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8425afdabd0bbe1ddc25d94716558a2e86b37206","datavalue":{"value":{"amount":"+0.9241612","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":"Q1076029$F6AB674B-14DA-42E4-A60E-F3A80E4A2369","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exact computation of Steiner minimal trees in the plane","badges":[]}}}}}