{"entities":{"Q1179749":{"pageid":1190498,"ns":120,"title":"Item:Q1179749","lastrevid":46221931,"modified":"2025-12-24T08:32:02Z","type":"item","id":"Q1179749","labels":{"en":{"language":"en","value":"Polynomially solvable special cases of the Steiner problem in planar networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25304"}},"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":"Q1179749$DF642155-FEAD-47E5-AFA0-0E517A9A40DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b85ca3628703e5e84be70f2e9329ecb661341378","datavalue":{"value":{"text":"Polynomially solvable special cases of the Steiner problem in planar networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179749$BC2FEB4F-73F7-405E-A737-6E4FDD748937","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a96a059b109cfa252b0618925c8270376126b6f7","datavalue":{"value":"0745.90071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$C4E32E22-DC33-4BD2-B3DB-9643CDCA0729","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26940fb60008b209b7f7ff0755e077e62c92e4e5","datavalue":{"value":"10.1007/BF02071979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$24308A03-4E8D-4C2D-92A8-9EBDAE55B061","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$6A18DC82-F3EB-4344-ADCC-1D9D74277EEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179749$B359A385-6A84-4E2C-845B-D2D4BA2DD5D1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"10df8c0446ecdfd0ac4d1bfbdd623aff683b203b","datavalue":{"value":"Given is an \\(n\\)-vertex graph \\(G\\) with edge lengths and a subset of its vertices. The Steiner problem on networks asks for a minimum length tree in \\(G\\) that includes the input vertices called terminals. The authors give algorithms for two special cases of the Steiner problem: (1) the underlying network is planar and all terminals lie within a bounded number of ``layers'' of a single face, and (2) the problem is the rectilinear Steiner problem and the number of rectilinear convex hulls in the entire ``onion'' of convex hulls is bounded. Both algorithms are based on the dynamic programming approach and run in polynomial time. Nevertheless, they have rather a theoretical significance, since the first algorithm can be implemented to run in \\(O(n^ 4)\\) time while the second has the complexity of \\(O(n^{11})\\) for terminals with onion depth 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$F2B01167-8BA2-42AB-B56E-1B0EE7886053","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$6517AF4E-4F82-4386-928B-0CAACECDC567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$A440CBE9-55C8-4EBC-A96A-CB00CE464BA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$070E0E1E-C91F-447C-B983-BBC282783119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$DD710528-D91B-4BA5-8D05-316377D4B0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$39B54C15-93E4-4E7A-B66E-96D8C6953618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$E4AE64C5-2CA4-4C69-9CF9-757827D59B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$2A4F2101-9489-44B2-ACCB-D73D04FE719F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$BBE91F2F-188A-4751-82BE-984BC4137FE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37c49d3021a77d987fa1de395aabfc97365015fb","datavalue":{"value":"25304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$A07E02E7-4F62-4DFD-A05A-B263E47391C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fff0b9b9390639a7771d62d84fadbb80da0482f8","datavalue":{"value":"planar network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$284A57A3-08F7-4F9A-A80A-98F096A21896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58870da1a411fbaea967c29271b1a9178ff50ec1","datavalue":{"value":"weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$B2D029C3-400A-4315-B78C-1FD1CB822369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89268e20a3b7112f7af2631dbe8d307aef9ba9fd","datavalue":{"value":"Steiner problem on networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$7AFA384B-B441-4137-BC29-22BCD93EF22E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41c1a76af6aecb8bfe6092f3b4de412cff54282b","datavalue":{"value":"minimum length tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$12B5590F-93B1-4CE3-BD4D-8C5D55CB03FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179749$336A67A5-9789-4EA6-8D74-2B3F640002F1","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":"Q1179749$F9B8E078-6E9A-4B4E-BA86-4B6A4FB961F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db91f50b8be0377b16c54636f8603d4272be2cda","datavalue":{"value":{"entity-type":"item","numeric-id":163023,"id":"Q163023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$543453BF-52EC-4038-B866-2225C333B7A6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$BF767C0C-07D8-44EA-9861-CB2B2451EFAC","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":"Q1179749$F1A3D4E3-DB90-4542-BC4C-19C8FAB7DF3D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a661769b64711d37b8c93fc0e62e6ad393dd736","datavalue":{"value":{"entity-type":"item","numeric-id":4206584,"id":"Q4206584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$54F054F8-8838-4CEE-9EDC-3E15018EC01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e11997a285ecc506111f12c0788a33d5899ea25","datavalue":{"value":{"entity-type":"item","numeric-id":3790663,"id":"Q3790663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$4C4EF3A0-5391-4AD2-AA21-53E261F947E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b7b4149100877ee54cdd1754bb9e9dac529d885","datavalue":{"value":{"entity-type":"item","numeric-id":582079,"id":"Q582079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$FAD94471-369F-45D5-B8A9-C1B33017D552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2e23d3b73f098eb67d4ecbedbc06122ddc75124","datavalue":{"value":{"entity-type":"item","numeric-id":5636923,"id":"Q5636923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$C10F34E9-93B9-424D-9B5F-60F66F0D4339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ad554d6e9a5d72d7d062638bea7b2e315785ea","datavalue":{"value":{"entity-type":"item","numeric-id":3820348,"id":"Q3820348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$178E703C-61EF-4A74-B01C-65A57261A18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$D9E3CB39-870C-4B10-8BDE-34591BDCCFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa4fad94b00c1283cfbf9a93a1abd9c2ff4c6dd","datavalue":{"value":{"entity-type":"item","numeric-id":5530464,"id":"Q5530464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$6F525442-7113-480F-9EB6-EFF4C26AB69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2117054e09e614a7a81e86cf8f22f23a4fea12ba","datavalue":{"value":{"entity-type":"item","numeric-id":5654074,"id":"Q5654074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$0B82C80D-EE77-4E70-B4CB-6743132C0A76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0172ba1b6d6a71dfada5ea07ead90ea9385b47a4","datavalue":{"value":{"entity-type":"item","numeric-id":3789369,"id":"Q3789369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$9D2D7030-7534-44D7-A33F-25579F27E708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3bd4903ca96601448c89bbb60098c06b73210b","datavalue":{"value":{"entity-type":"item","numeric-id":3816989,"id":"Q3816989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$1C8A4575-4365-40EF-AB3A-7548A2BED5F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4fb5851f61868ae4bb5972a4c16eeedeaccbae0","datavalue":{"value":{"entity-type":"item","numeric-id":3779760,"id":"Q3779760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179749$961B6E7A-959B-4C53-93BA-FFAA7E08041D","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":"Q1179749$AB643A86-15C2-4DED-8996-3EBD8CB3BA39","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bcb1bfb2fcc293ec66cd57d65efd782f6a5c7437","datavalue":{"value":"https://doi.org/10.1007/bf02071979","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179749$FE6A3E5F-25B9-4C3D-A7CC-6BC60ADE5336","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ed6c6a39f8cd39d67ce79bc815eb05b5bf4b19b4","datavalue":{"value":"W2066137891","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179749$57382AF2-4704-4856-8B8A-194D9FADD1C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6895f491fb3f48155ed10b6029d4e628b3728a19","datavalue":{"value":{"entity-type":"item","numeric-id":4242784,"id":"Q4242784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d90078ddb1649cbc41768435d309c563e97f348","datavalue":{"value":{"amount":"+0.8421477675437927","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":"Q1179749$2CC801EF-7681-4063-81F9-986F917C3051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81a2a393b4096f5d6e8d8082987e43ecad0ad647","datavalue":{"value":{"entity-type":"item","numeric-id":4206584,"id":"Q4206584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b40e56449f819205ee31426472c1ff6e0387034","datavalue":{"value":{"amount":"+0.835826575756073","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":"Q1179749$FE429516-492B-48CC-B157-F29721BCB596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99a12f30363594abc52fe4bb34cdefd766706640","datavalue":{"value":{"entity-type":"item","numeric-id":1123630,"id":"Q1123630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a2c2009c3b501f7d551265f8174b4f70c1277d1","datavalue":{"value":{"amount":"+0.8355366587638855","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":"Q1179749$BACD9ED8-A89D-4803-BDDB-DDB63D396CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d615acfb039d2034888e72f65ae27a807a60a6d5","datavalue":{"value":{"entity-type":"item","numeric-id":1566725,"id":"Q1566725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"278b3fe0a30c40c96c54f9401bb338b0d38fd607","datavalue":{"value":{"amount":"+0.8291339874267578","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":"Q1179749$BAC00851-23F2-4162-BCF0-EC9011F84EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbdea4ce85821bc80f520cb5799cadafbcdee462","datavalue":{"value":{"entity-type":"item","numeric-id":3693291,"id":"Q3693291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3eb5394bded89e357b689b07ff3295b0d23871d4","datavalue":{"value":{"amount":"+0.8230884075164795","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":"Q1179749$2719E5F5-DEB4-421F-9566-E57C85546587","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1179749","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1179749"}}}}}