{"entities":{"Q2632008":{"pageid":2642751,"ns":120,"title":"Item:Q2632008","lastrevid":53426696,"modified":"2026-01-24T22:51:35Z","type":"item","id":"Q2632008","labels":{"en":{"language":"en","value":"A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7056083"}},"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":"Q2632008$95AB8F08-2EF6-4595-9F75-58B949C634C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1fe6a339c9f1e8df469a92b05a4065d4c188ba2","datavalue":{"value":{"text":"A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2632008$226052B7-7E54-462D-A069-336656F0B4CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd982699f713560c05e6aed84b7b010006b00439","datavalue":{"value":"1426.68307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$8FB1642F-9BF9-49FC-BED6-3B08D449BEB3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b90eaa5df1089aeaf6a0dd0c7cbaab65f37a1ab","datavalue":{"value":{"entity-type":"item","numeric-id":2025055,"id":"Q2025055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$E1F755C1-6A58-4FDE-A6E8-F75374B2884C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"efadffffbc67edfcfbbc3e4225f7ff3ff7c09695","datavalue":{"value":{"entity-type":"item","numeric-id":324739,"id":"Q324739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$A75C106C-16E9-4C61-9A89-F8EE552F42CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$2B1CCFDD-C3A0-4AB5-A566-14E9788C3638","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ff447296bef390af9bbc2815788c2e74961068e5","datavalue":{"value":{"time":"+2019-05-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2632008$7DF52394-52FE-48FF-AE58-6580F5AC4CF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2da2119e1badcdd389572fb8a7020fe1e8a4273","datavalue":{"value":"The paper presents a polynomial-time approximation scheme for the metric case (edge-length satisfying the triangle inequality) of the optimum weighted source-destination communication spanning tree problem (WSDOCT). As this is mainly a theoretical result due to unpractical PTAS complexity, the authors also present an \\(O(n^2\\log n+mn)\\) 2-approximation for the problem which improves the time complexity required by the PTAS to achieve the same 2-approximation.  The WSDOCT optimization problem is formally defined as follows: Given an undirected graph \\(G = (V, E)\\) with non-negative lengths \\(\\omega(e)\\) associated to the edges and non-negative weights \\(\\sigma(u)\\) and \\(\\rho(u)\\) of nodes \\(u\\in V\\), the objective is to find a spanning tree \\(T\\) of \\(G\\) that minimizes: \\[ \\sum\\limits_{u,v\\in V}(\\sigma(u)\\rho(v)+ \\rho(u)\\sigma(v))d(T, u, v), \\] where \\(d(H, x, y)\\) is the minimum distance between nodes \\(x\\) and \\(y\\) in a graph \\(H\\subseteq G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2632008$5171F454-7462-4792-9A58-01751C1AD07B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$9E37BC9D-A9FE-4074-8452-9DC25187E471","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$F5342BE9-A648-49E3-9739-2B79F326CDCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$D158A8DA-FA96-43A8-8D3D-B5B14E498F2F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8dbba396be0538e4642a3f580e1b149c08635c74","datavalue":{"value":"7056083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$DB9C0367-642A-4F8C-A2CC-97C57448385B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d7b7cddd239e1044308dd8fe3f6ab83c27bae39","datavalue":{"value":"optimum communication spanning tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2632008$D8DE8AC0-860F-4366-98EE-4672189FA6EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2632008$04148703-D3DA-4F2A-B4E6-78331D955958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"600c1e6cd816b63470df7d348a4275d1b81cf52a","datavalue":{"value":"polynomial-time approximation scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q2632008$7E0E8991-0A42-4E88-B066-1372D658B324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d39a84e65ae219419f0302b7d226049d96b35191","datavalue":{"value":"metric problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2632008$6264AB33-F178-4AB1-A4B9-2144B7E92C41","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":"Q2632008$255E1DB5-629E-418D-BFDD-471B0C944C9A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7661f0f269504a3a780b100b9cd649f0cdd60e47","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2018.11.008","type":"string"},"datatype":"url"},"type":"statement","id":"Q2632008$8C52CA1C-5396-40F4-82ED-B500CA67F949","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1f6865a6807c9cbc3b7663785547d50b815e0e5e","datavalue":{"value":"W2901018354","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$84E40149-78CE-4DC2-BEA9-CF5B66E5D9B9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bacd35466b59e39ecadd37c4d20c68a3074d7ee4","datavalue":{"value":{"entity-type":"item","numeric-id":476426,"id":"Q476426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$1F56FA5D-C404-4AB4-8B7B-B318C99617CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a1a0f2ea7d712893da782bca43414ca4f389a95","datavalue":{"value":{"entity-type":"item","numeric-id":3295505,"id":"Q3295505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$AAB1ACD4-3899-4FDB-869C-A54164F4F8CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$5F6DBFB1-9490-424F-B8DF-4910A402CAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aea5ea7a9985472c080840895d0fc552e3d7cf9f","datavalue":{"value":{"entity-type":"item","numeric-id":3212880,"id":"Q3212880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$E49ED083-25FF-41C9-B30E-7E9910569493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa99331db23e66381b9e84d4b5de6c6b6c83240","datavalue":{"value":{"entity-type":"item","numeric-id":4178943,"id":"Q4178943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$7B53E3C8-6FED-4200-8A60-41FB3FE43E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b8f37a1e7d2ddb5b4d7a11d0fd9ef9739a4370","datavalue":{"value":{"entity-type":"item","numeric-id":5288156,"id":"Q5288156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$E992825D-2853-445C-B545-7A59BA2150D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0ce4896ae0b4cbfea64b70889bb6381f18d7b89","datavalue":{"value":{"entity-type":"item","numeric-id":5176579,"id":"Q5176579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$FF353F0F-1D53-4AB2-BBF2-72FB8AC78252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aa548bc8a9103d7dbc2996565dda6d2bd06cd20","datavalue":{"value":{"entity-type":"item","numeric-id":2357170,"id":"Q2357170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$0C5E724A-AA73-457B-AF04-E0EA71BE4D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95672c743a77218c6d02ab7cc752b972964f1d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5901089,"id":"Q5901089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$6F10EEE8-A1BC-46E8-A013-175514561F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"133b4f28a7f10ee09b8010771103ce87b0f46337","datavalue":{"value":{"entity-type":"item","numeric-id":2479532,"id":"Q2479532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$2BB44811-C0DA-4A49-8C69-85EBA340AF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e58deb37e3fa908a3f7c4f90f6b04ecac22098c0","datavalue":{"value":{"entity-type":"item","numeric-id":4805401,"id":"Q4805401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$BC770404-7F99-4D01-83E0-6117F366FAEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea528b82d6d3921a053f219d22f0f3a874568f9d","datavalue":{"value":{"entity-type":"item","numeric-id":1566575,"id":"Q1566575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$CBC576D0-E0E5-45DE-90B0-8E4CA8BCA928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0434d3c4688d592fd7bc1ea9fc03400c8c4b0bed","datavalue":{"value":{"entity-type":"item","numeric-id":4500852,"id":"Q4500852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$FDB3898E-BCB8-41B2-9E40-B0828A5D53D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14175423d83b5bd6bfeffb63cc57431a80a731ed","datavalue":{"value":{"entity-type":"item","numeric-id":4943844,"id":"Q4943844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2632008$C4E847E4-383E-4FF8-9F26-6D22CDE1223B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a9829552f576d0963d44d7bfd6233b6f3f547461","datavalue":{"value":"Q128930595","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$21D421E9-52DD-442C-9FF0-8A7B26A35E9A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e28f5e56e566dd6b1efa0c473fb4e6e9ce2ea726","datavalue":{"value":"10.1016/J.TCS.2018.11.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2632008$2BE1FC37-FA17-4251-A38D-E2EE1AC66E38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3802914383e003e279573aaca9c7a7e8c5461f5","datavalue":{"value":{"entity-type":"item","numeric-id":5176579,"id":"Q5176579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f81cb0e58383c3f51fd39849eea54dcde42915ed","datavalue":{"value":{"amount":"+0.8968127965927124","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":"Q2632008$E1A4B0F9-E856-4701-9705-417D0BA39745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64bb1164202433f967a5ea5dc1267b054190bd69","datavalue":{"value":{"entity-type":"item","numeric-id":2357170,"id":"Q2357170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5321dc6c665e05af0a26c02c58b15c5c5450c7a8","datavalue":{"value":{"amount":"+0.8900949358940125","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":"Q2632008$39C81BCD-0083-4132-ADD2-45CACB1E087A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99d1673d0f13d22d8587f71691c3d0b561746cd0","datavalue":{"value":{"entity-type":"item","numeric-id":5174945,"id":"Q5174945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1899d01748eea0c600f0a4a64504995a778c3832","datavalue":{"value":{"amount":"+0.8893938660621643","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":"Q2632008$11E686FF-B82D-4647-A310-4AC70A594A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b3d7cd3eb62ca38d4cdf259d90a50fd89325bc6","datavalue":{"value":{"entity-type":"item","numeric-id":1887037,"id":"Q1887037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d15ce933898105a87f43f551bc3267ba2422390a","datavalue":{"value":{"amount":"+0.8608558773994446","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":"Q2632008$15C9FCA0-E2B6-4859-B876-50664B9C0A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac43252618c5b7ef877964721b10e7e614f7c808","datavalue":{"value":{"entity-type":"item","numeric-id":1566575,"id":"Q1566575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4bd801fd83116b0318285aec82a6b66f2164f79","datavalue":{"value":{"amount":"+0.8403820991516113","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":"Q2632008$41466B38-6D60-48B3-BF3B-E38820D4FC7C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2632008","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2632008"}}}}}