{"entities":{"Q5953596":{"pageid":8130398,"ns":120,"title":"Item:Q5953596","lastrevid":47729455,"modified":"2026-01-02T13:29:26Z","type":"item","id":"Q5953596","labels":{"en":{"language":"en","value":"Grade of service Steiner minimum trees in the Euclidean plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1695188"}},"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":"Q5953596$09BF313C-31A2-4479-8644-EC180C9923C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"895b9327c2acc0b30766e45359b2cc62f85840c5","datavalue":{"value":{"text":"Grade of service Steiner minimum trees in the Euclidean plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5953596$EE19920F-933C-4013-8095-B8C00FFBB67F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81d9090a0ef35988f11d1dd75985c2d5584a4816","datavalue":{"value":"1041.90007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$8B6F7CC6-07CD-4F74-824A-DAC9606C4F8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0391b7c4dfba8c377da7d81f897d3cf43a7a75ee","datavalue":{"value":{"entity-type":"item","numeric-id":166207,"id":"Q166207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953596$28FC0ED2-F143-45AF-9634-2ECEC1C8B2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8444ef2e9dd4226196ce672b5a484f78760db07","datavalue":{"value":{"entity-type":"item","numeric-id":166205,"id":"Q166205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953596$9B12FF6D-C2BE-4BA8-8CCB-C81EA4CFE2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953596$E4B92816-903E-4917-85D7-18D919795C83","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":"Q5953596$AE88CB00-7EC3-44A8-B580-3AF494F2455C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d6f630a8f9062cc7a61bf0b0d4072e8f242af2b3","datavalue":{"value":{"time":"+2001-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":"Q5953596$6853C9DD-C048-43A4-8C9F-8A9664CF7704","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93a3ae9648a44a5b807bcac8d655f4c817b86f95","datavalue":{"value":"Given a set \\(P\\) of \\(n\\) points in the Euclidean plane, service requests of grade \\(g(p_i)\\) for each \\(p_i\\) of \\(P\\) and unit costs \\(c(g)\\) for each grade of service \\(g\\), the Grade of Service Steiner Minimum Tree (GOSST) -- problem asks for a minimum cost network, interconnecting \\(P\\) and some Steiner points in the plane (with service request of grade 0), such that   (1) Between each pair of points \\(p_i\\) and \\(p_j\\) of \\(P\\) there is a path.   (2) Each edge \\(e=(p_i,p_j\\) of the connecting network is assigned a service grade \\(g(e)\\), which is no smaller than \\(\\min(g (p_i)\\), \\(g(p_j))\\).   (3) The cost of the network is minimal among all networks satisfying (1) and (2); the cost is the sum of all edge costs, where an edge \\(e\\) with service grade \\(g(e)\\) induces cost of \\(g(e)\\| (p_i-p_j) \\|_2\\). Similar to a proposal of Mirchandi for GOSST problems on graphs, the authors present a recursive approximation algorithm (RAA) and prove upper bounds on its worst-case-time-complexity at least for those cases, where there are at most 3 different grades of services.   Next full Steiner topologics and their realisations are introduced and it is shown, that there is a full Steiner topology inducing a GOSST. For a given full Steiner topoly the grades of service for all edges can be computed in linear time: an \\((1+\\varepsilon)\\)-approximation of a GOSST is computable in time polynomial in \\(n\\) and \\(1/\\varepsilon\\). Although the number of full Steiner topologies is much less than the number of tree topologies a partial enumeration technique by backtracting may fail in large-scale-instances.   The authors prove a bounding theorem, using topology vectors introduced by W. D. Smith, and propose some heuristis for the initial upper bound and for pruning subtrees in a branch-and-bound-framework; but experimental results show limited applicability. Therefore the authors propose a \\(k\\)-optimal heuristic algorithm -- with surprisingly good results, but no complexity analysis is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953596$6782EAEF-86BE-4D70-9816-E36B460E83C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5953596$5E09CD96-CEA0-49C3-A609-3B4ED02C14A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e3ec0ebb66ad9a53653ec1e19a7608e786acef46","datavalue":{"value":"90B18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$7A5609C2-10A9-4EBE-9E76-85312E24A994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$A9B2B99E-3904-45E6-B05B-448A8E5329EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$E138E28A-854B-4CB2-8259-5D9CF3F4366F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e68c9ac956d8e514a113ba677cf68922c5a6397","datavalue":{"value":"1695188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$5618C958-8B61-4B89-8E72-1A09B7338411","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b490dda2b09dc51284d3fc8298d846b7202202","datavalue":{"value":"Euclidean Steiner minimum trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953596$610BF7A3-91BF-4AF1-BBA7-95B1D01907B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba3671326ab8a9b195aa9f697d844ba2c120b538","datavalue":{"value":"approximative algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953596$9E852428-DFE5-40D8-B8D7-DB0526B0D4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5796cd88a29d87fef35e18b378719c76dde1caf2","datavalue":{"value":"grade of service","type":"string"},"datatype":"string"},"type":"statement","id":"Q5953596$2A53E204-18C5-468F-AA90-6EAF7F2E6827","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":"Q5953596$20825D84-06D1-4DAE-90AD-222300E6D96D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"968a4ed82d90e8013e921f564ed7c8f1ab1bdb32","datavalue":{"value":"https://doi.org/10.1007/s00453-001-0050-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q5953596$E8321023-6818-4AD5-946A-F1FD28D73E6B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a73cc6609deb4ee1353ac381df77aa617a3d5652","datavalue":{"value":"W1536432301","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$7E029F02-B096-436A-BCE3-329931952C83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7037efac5a86d988e7e8a7140770bd4e26950f78","datavalue":{"value":"10.1007/S00453-001-0050-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5953596$9FC881F6-267E-4594-9D94-D6D63438D61B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fc62e22fccc517b07d95028cbaea0bf096963a8","datavalue":{"value":{"entity-type":"item","numeric-id":4945799,"id":"Q4945799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac0eb4a5307f4486b64302e3d6627a36c5089ff6","datavalue":{"value":{"amount":"+0.8551364541053772","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":"Q5953596$5769B061-EDE1-4E6B-B0CF-45A26AB55A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eecfb3330089d464f0075d0b7a4164e59951027","datavalue":{"value":{"entity-type":"item","numeric-id":1202044,"id":"Q1202044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8cf7ab806aee05d7e21845342a459b7281a2016","datavalue":{"value":{"amount":"+0.8011265397071838","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":"Q5953596$AAFF069A-847C-4D1D-9B18-330EEA9D1827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f33a31388c9d9f1a45e619b229207da369a3af2f","datavalue":{"value":{"entity-type":"item","numeric-id":3713880,"id":"Q3713880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8cf7ab806aee05d7e21845342a459b7281a2016","datavalue":{"value":{"amount":"+0.8011265397071838","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":"Q5953596$628D2652-2001-4F29-A8B5-2E2C774AC1E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9957f07b82cbec710821e509b9944c9eea0d1e0","datavalue":{"value":{"entity-type":"item","numeric-id":687085,"id":"Q687085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ff2df39e1672360489afb78a815cb64f0fe3e5a","datavalue":{"value":{"amount":"+0.8006030321121216","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":"Q5953596$0E4B96FA-406C-4B1F-AA8C-99EC57EA477E","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":"52d5e01661e65f20aae3760cdb1ebec248392851","datavalue":{"value":{"amount":"+0.7996942400932312","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":"Q5953596$0FED8D72-E30C-4155-B1BF-7BE9AFE03E35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5953596","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5953596"}}}}}