{"entities":{"Q1105495":{"pageid":1116244,"ns":120,"title":"Item:Q1105495","lastrevid":66142212,"modified":"2026-04-12T07:50:01Z","type":"item","id":"Q1105495","labels":{"en":{"language":"en","value":"Two probabilistic results on rectilinear Steiner trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4059142"}},"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":"Q1105495$EE5DF975-085D-467F-BEFE-8D99CDF75B9D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f870914ab0681340dc689ef7ccd37407375b6e7f","datavalue":{"value":{"text":"Two probabilistic results on rectilinear Steiner trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105495$246B8130-5203-4134-8932-0D666D9D5723","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bc0ad58c1b98c1439c1e988ed42ec4be032a2a3","datavalue":{"value":"0648.90080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$6DAD8618-83E1-468D-8F36-BCB59FEF6E08","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b393d5e3adf47e1ad90af73ddca882eca4db5ec3","datavalue":{"value":"10.1007/BF01762114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$52D32B90-E736-40A3-9FA3-8EDF4097E31A","rank":"normal"}],"P16":[{"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":"Q1105495$C0FCC975-0082-4385-88F6-EC1CE13A46F2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$822AA922-3AFA-4D08-A812-AAD6B9F6B188","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":"Q1105495$B066DAAA-C42C-4278-9917-2C04F3608CE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e08e9c824f9f37859bee2e1bff3b223fff00921a","datavalue":{"value":"Given a set V of n points in a plane a Rectilinear Steiner Tree (RST) is a tree that contains V as subset of its vertex set and allows only horizontal and vertical edges. The vertices of T not in V are called Steiner Points. The problem of finding an RST with minimal overall length is NP-complete.    The author develops a new heuristic for the RST problem and shows that the expected length of the RST given by the new heuristic is for large n at least 0.098 \\% shorter than the expected length of the minimal spanning tree heuristic.    Moreover he proves: For large n, the expected number of Steiner points in the optimal solution of the RST problem is at least 0.041\\(\\cdot n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$201FF5B7-21F8-4FC9-861B-9281C8C42585","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$70F84395-D25B-4BB4-9149-C67CC036AD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$E50D37BC-306F-4B00-89DD-D91E31C09C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$263B0E13-7A49-4E9C-A557-C7BB093C6EA2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d29cdeceb1cc48717862c5409bc8a9f440acf1a","datavalue":{"value":"4059142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105495$4A5E85CE-2C11-407F-A318-BF122C6F76D4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8229caab24c4a204d7d14b4266254ec87c1e693d","datavalue":{"value":"Rectilinear Steiner Tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$BFFA1765-AB6F-4240-87C0-DD5EA1C111A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54730962b211f49276386d9cd297304fc1dcd28d","datavalue":{"value":"Steiner Points","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$67AC24C7-2BAA-431C-8F4D-2F5471BC12D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d2ff381f49046948d5f7a3706afed33c7aa2044","datavalue":{"value":"minimal overall length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$7ACE44BD-0BA3-4480-8945-14A3015C032E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a7f128a8890c1ed831720a74faec8d6c0dd504e","datavalue":{"value":"NP- complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$188DCAD2-8482-4D6D-9BDE-71AF348BAF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$F3946582-C27E-45C5-82B9-1AC3B593DDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6078fceba255c2f14830c9cbf81b3ab69e83b898","datavalue":{"value":"minimal spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105495$6FF4DFCC-EAFA-4A17-95A2-3FC009D576C2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c24d1a4d9566abc9461048333a6d2676bb28f451","datavalue":{"value":{"entity-type":"item","numeric-id":166234,"id":"Q166234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$ED0E3430-075D-4CAF-83EC-E9D30B9F75EE","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":"Q1105495$9F8BECD2-91CB-418E-8B05-522C8F9C81AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d72aff706ad554ae747630a2259b0d46154bdd7","datavalue":{"value":{"entity-type":"item","numeric-id":4120589,"id":"Q4120589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$473E0342-A947-42AE-B02E-26EBABFD0BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94765fb846bed352148d9e13a9cf76ce38cb42b1","datavalue":{"value":{"entity-type":"item","numeric-id":1159677,"id":"Q1159677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$725C49ED-151A-4158-8866-D97DB88C6E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7b7c13f8756ac0aac8a4f3631a388b8627f48a5","datavalue":{"value":{"entity-type":"item","numeric-id":4186240,"id":"Q4186240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$F847BAAA-7D63-4E0D-B07B-903083499A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$2A0804C8-F9BC-4A1D-8DFF-7FE6897A6EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cff460e5532d881b857f2a3d6565f94019b1cbd","datavalue":{"value":{"entity-type":"item","numeric-id":4083448,"id":"Q4083448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$B38F5962-2A3B-4486-8A4C-1A618939F627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"274e588a53e833ba083cd607d96c6701e58330a5","datavalue":{"value":{"entity-type":"item","numeric-id":4174637,"id":"Q4174637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$C991236C-EE1C-42ED-8090-2F3364232377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83b240b9d994e7c2f1d40ca3e95aa7de34e24583","datavalue":{"value":{"entity-type":"item","numeric-id":3707785,"id":"Q3707785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$6297E657-0AD7-41DC-900A-131E195E572C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35af7e23a3b21efab10de1211204624cdd5b24b7","datavalue":{"value":{"entity-type":"item","numeric-id":3789373,"id":"Q3789373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$CC534EE5-628F-4001-A965-9C9936D66656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$5CEE8C0F-FA36-43A7-9AB0-DAC9F63F2BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$AC3B2677-A462-431E-BEFA-589C505EC243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc1b2428ce601dbfce8295389c70645762fd90f","datavalue":{"value":{"entity-type":"item","numeric-id":4110824,"id":"Q4110824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$D176BDA2-7DF7-4F63-AF82-1275B739115C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba7cd00e32cc22a9798adad72194a8335764089c","datavalue":{"value":{"entity-type":"item","numeric-id":3252881,"id":"Q3252881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$03572823-6B69-4933-980A-6BD88A77D0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84185c1cc8c1d738d9f2dc4d7ca5384415ffdbee","datavalue":{"value":{"entity-type":"item","numeric-id":3922181,"id":"Q3922181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$C8324BE4-579B-4CA4-9957-1033EE9B0DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd9c902e18f256ef6ab9ecbbe60131e5487ac544","datavalue":{"value":{"entity-type":"item","numeric-id":1152627,"id":"Q1152627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105495$A8C9DF0E-E5C7-488E-A169-1B8C373DA8A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899d8cd39dbfe2bb871133a103b884696f946170","datavalue":{"value":{"entity-type":"item","numeric-id":1118419,"id":"Q1118419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4995ada5fc069075f53874208fb9d747ac28aa3a","datavalue":{"value":{"amount":"+0.8733859658241272","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":"Q1105495$AC61E494-9438-4402-A7F8-5CBF7429B432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dfb6a1cce095bb4500397ca2fb41d608c9d5426","datavalue":{"value":{"entity-type":"item","numeric-id":3789373,"id":"Q3789373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c693231085c43e61c7758f447eb2063b5ca96369","datavalue":{"value":{"amount":"+0.8491935729980469","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":"Q1105495$9EA81F19-8F98-462A-9AA1-451C5F61D9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf78af1a11d6cff4dd774569f7c88bf6ef02e636","datavalue":{"value":{"entity-type":"item","numeric-id":1969944,"id":"Q1969944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b75ecf375e255ba9fdf58142bff979f125dc6fad","datavalue":{"value":{"amount":"+0.8471230864524841","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":"Q1105495$B45CDF7E-258A-4152-BC4C-44A1D84D02F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3833612293a856bd35bae1fa45ee2388a90c72de","datavalue":{"value":{"entity-type":"item","numeric-id":3838231,"id":"Q3838231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"055c3c0008469adb809e35efd9d41d7d7fc1d5dc","datavalue":{"value":{"amount":"+0.8444492816925049","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":"Q1105495$83066168-F1C6-4908-A059-723A53BB5405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"064468ffeda579263680afdbf424ee04e6e02a92","datavalue":{"value":{"entity-type":"item","numeric-id":4698230,"id":"Q4698230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70f60669044b8a7d04bca3961416716d60e9a91c","datavalue":{"value":{"amount":"+0.8418559432029724","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":"Q1105495$1FA908C2-A419-4689-808D-0A6F87FDF955","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two probabilistic results on rectilinear Steiner trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_probabilistic_results_on_rectilinear_Steiner_trees"}}}}}