{"entities":{"Q1969944":{"pageid":1980686,"ns":120,"title":"Item:Q1969944","lastrevid":47461852,"modified":"2026-01-01T19:45:23Z","type":"item","id":"Q1969944","labels":{"en":{"language":"en","value":"On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1417532"}},"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":"Q1969944$40D412D7-978C-4DAC-A310-859F073410DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e80bc75ad516f60c381fb94b206030bc3f0336b4","datavalue":{"value":{"text":"On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1969944$1B6EED2C-E7EA-4328-8BCE-C97B8761AD80","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e629552ddb5d02e71b79868c9291a4b1d177a7e6","datavalue":{"value":"0951.68101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$5E3F5466-5E7F-4718-9E23-0BBCBE6D5AE3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e947c4fb3921699925780ed35d41c9af62d536b","datavalue":{"value":{"entity-type":"item","numeric-id":344818,"id":"Q344818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969944$5845F820-8B6E-4C74-8F58-790821034164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"937386a4c2f43cfca2018b99d2966def39c6b138","datavalue":{"value":{"entity-type":"item","numeric-id":826085,"id":"Q826085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969944$BF96651D-3759-4F3B-9FF7-97318150B82C","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":"Q1969944$5D1F2F7D-3E74-4914-A7B8-77799BF929F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1969944$CEED6A55-66AF-4B70-A514-584011594833","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c2582dc557253cfa508f0ce84957c4c02f05422","datavalue":{"value":"The rectilinear Steiner tree problem asks for a shortest tree connecting \\(n\\) given points in the plane with rectilinear distance. The authors present a dynamic programming approach to this problem with worst-case time bound of \\(O(n^2 \\cdot 2.38^n)\\), and for random instances they prove a running time of \\(\\alpha^n\\) with constant \\(\\alpha<2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969944$2A5E75A3-62A2-4EDB-8E33-5185B41A31D5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"094d61d1ff99e208b2511ef0c6fc952ca4052a28","datavalue":{"value":{"entity-type":"item","numeric-id":230778,"id":"Q230778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969944$A2FD68EC-24DF-4497-BCB5-F3A2437313D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$82F223C2-F42B-429F-A3FB-8F1AB3CF529E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$DDB66904-9A7C-4953-80AF-D845CE0F8817","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6688a4f31c68e17d39737bec3909c34e4a3168aa","datavalue":{"value":"1417532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$EEA8791B-F22C-41E9-AF75-2EA6E17E05BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6596c6644a2df6136af0b3d72e6fb93a5a921964","datavalue":{"value":"Rectilinear Steiner trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969944$9928C6C4-C0EC-4327-867B-0D8A7C40DBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969944$98679ED2-1A5F-4BD6-9536-CF988A0093CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969944$A3B21290-DA1D-4D08-AE3B-544461BE5E04","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":"Q1969944$658620E9-ACA7-4E82-B83E-E4BE057F623A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"01b0b1c5a7bb5f0a0e2a3971fcea670ad233098b","datavalue":{"value":"https://doi.org/10.1007/s004539910005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1969944$0D2D4466-5C74-4157-8B3F-30023596459A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a16756b4272202bcd8b327274e19ae221ce4612f","datavalue":{"value":"W2066933505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$672E54DB-7E54-4EA0-AC81-CB99856B3745","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a0290c6facf87348d9027562aa81114ee59b03b","datavalue":{"value":"10.1007/S004539910005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969944$246404D5-B741-4CC8-8614-C858783C7860","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcc5085a765dde1b162b5a3d2b379252a0fa7308","datavalue":{"value":{"entity-type":"item","numeric-id":826086,"id":"Q826086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cab4f7dde819510cfddba0c68d06c64939b7258","datavalue":{"value":{"amount":"+0.9435386657714844","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":"Q1969944$9FDB6F80-D472-4869-8C61-F9F5998F5660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a484c66a99bb372cb0e1cf3de34f4c84e931dcd7","datavalue":{"value":{"entity-type":"item","numeric-id":4365027,"id":"Q4365027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"737d619b76391dc73c638f06762e7370aa53a5cf","datavalue":{"value":{"amount":"+0.8672569394111633","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":"Q1969944$C5580751-4E8A-4947-9AB2-A4E7CEC94538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38f18a758e019c51e4852cdaa950e169c70e5ee","datavalue":{"value":{"entity-type":"item","numeric-id":1276966,"id":"Q1276966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9338c0d3789bf4309a750d8cd47fc94559c1e71b","datavalue":{"value":{"amount":"+0.863338053226471","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":"Q1969944$83EAB89D-3E95-4F8F-A783-CFB879ACA467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4e191e3ef3907b36dc54d0ab47354579d1f86e4","datavalue":{"value":{"entity-type":"item","numeric-id":1966510,"id":"Q1966510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a88b2daf2f5afe99654adfba10f9c26de48bbc05","datavalue":{"value":{"amount":"+0.8623142242431641","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":"Q1969944$428C3B62-B94E-47A1-B803-8A4AB998C655","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":"696d43b42184da40fc346c6b82a67c0ed75f0327","datavalue":{"value":{"amount":"+0.8597829341888428","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":"Q1969944$6C1E54E3-DEF5-4072-B2AB-AA02F4CC3272","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1969944","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1969944"}}}}}