{"entities":{"Q557826":{"pageid":559593,"ns":120,"title":"Item:Q557826","lastrevid":48508090,"modified":"2026-01-05T01:26:52Z","type":"item","id":"Q557826","labels":{"en":{"language":"en","value":"Approximating \\(k\\)-spanner problems for \\(k>2\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184056"}},"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":"Q557826$EFF969E5-F3D2-43CE-B960-635AD9B98172","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e628c0539b20803ead5f78c36164751f340d5fba","datavalue":{"value":{"text":"Approximating \\(k\\)-spanner problems for \\(k>2\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557826$E9B2725B-726E-4F6E-8ACE-D4C9A40B070A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b80887b2d1c9d8ed0d8fae23ce1760e336c18829","datavalue":{"value":"1075.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$EB3514DA-522C-4C7D-A0A6-7C3EC350A8BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"39573f0f48d13864985e6576ba30c12f9be5dca4","datavalue":{"value":{"entity-type":"item","numeric-id":265068,"id":"Q265068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$5283E3A9-5A2C-4739-A74C-BE2726DA79D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27618d3afb5e8d09bd379eb0df3ccd8566897b24","datavalue":{"value":{"entity-type":"item","numeric-id":244948,"id":"Q244948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$C0F62199-D047-4593-B0BE-52DE4903215D","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":"Q557826$672202E3-CF84-4A12-BBAE-C4327C056E5E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q557826$210B7B32-2DA6-46F1-A69D-D6E7BDFC72A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c3058c2a28385c3950855d200f93b423e96e69b9","datavalue":{"value":"The basic \\(k\\)-spanner problem is to find a sparse spanning subgraph \\(H\\) of the input graph \\(G\\) such that \\(d_H(x,y) \\leq k \\cdot d_G(x,y)\\) for all vertices \\(x\\) and \\(y\\). For this problem and variants thereof the authors list known (in-)approximability results, and generalise the technique of \\textit{G. Kortsarz} and \\textit{D. Peleg} [J. Algorithms 17, 222--236 (1994)] to \\(k>2\\). See [Integer programming and combinatorial optimization. 8th international IPCO conference, Utrecht, Netherlands, June 13--15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2081, 90--104 (2001; Zbl 0987.68052)] for a summary of the preceding conference version.","type":"string"},"datatype":"string"},"type":"statement","id":"Q557826$A866690D-B746-4D05-92A6-FF080A23EDF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$05E3CDEE-43B4-42E9-8F91-A28ED2AED880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$562ED878-DCBD-4231-A6B9-AC27B2322AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$900BEE8D-9FC6-4020-81F5-E6D28547C6EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$532B513F-DDAC-4009-85E6-A57E9184D360","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fbe21a26e6b351b45914bda952120203524e499a","datavalue":{"value":"2184056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$A5033709-BC99-4021-961E-AAC35F2F91F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q557826$46CACAB9-4F74-409E-9BA2-1EB3EE7CA723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q557826$F87DD381-A72E-4F5A-88CB-2AAB0B471956","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":"Q557826$34FB4F58-772A-43E1-86F1-678F4000D66D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5423d862fdc7aa72611e5226ddcba22d0ba55a1b","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.11.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q557826$B330EAE7-67AD-4D82-914C-390195ECC4C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d0ead1d41140bece1499c98f1b289b0f8901f514","datavalue":{"value":"W2044989918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$50D3132F-D505-49E0-A2CF-6404D2D936F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98bc9d135c428af9615580e4c359203be687b709","datavalue":{"value":{"entity-type":"item","numeric-id":5056089,"id":"Q5056089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$286C8B48-5D3D-47B6-A750-46E8CFBA8B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$59287C1F-0126-4E96-8E54-3159BBB74848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0942b7eb9cd2fbcc3749cd648795867620d0ffda","datavalue":{"value":{"entity-type":"item","numeric-id":1315465,"id":"Q1315465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$3D52AB64-7A87-46DC-AB43-221B1D93F621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d45dd5b8ccb621e6aefa5f5d6b3a28b45bc431","datavalue":{"value":{"entity-type":"item","numeric-id":4847362,"id":"Q4847362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$206FD889-9CCD-43B7-81C1-AF62149B9D2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c9eacc230c472857cf176516274a05ea28f03a4","datavalue":{"value":{"entity-type":"item","numeric-id":4698355,"id":"Q4698355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$B65CD6AB-AB4C-44CF-8C0B-2AC44BBCEC56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffc7c8b334d26c0686dd1a9b8ac5d7d5836aced","datavalue":{"value":{"entity-type":"item","numeric-id":584279,"id":"Q584279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$4F8B246B-7028-4F48-B8D5-A5FDAC4E2014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b25b274e4c418261ded7cd1fc46a8f9c565112b","datavalue":{"value":{"entity-type":"item","numeric-id":4943891,"id":"Q4943891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$BE51DBAB-AB34-43F8-981E-D751DBD4072B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4992847d5aeb886160609f49ac6f7e606a35f3e1","datavalue":{"value":{"entity-type":"item","numeric-id":2728855,"id":"Q2728855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$38B227E1-2057-4C44-B73B-887697B37799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a796034671f1d07728ab79c68e82e75fec096b1a","datavalue":{"value":{"entity-type":"item","numeric-id":2754183,"id":"Q2754183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$628FD159-EA45-4DF9-8841-D21B4A03EF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e77617a4d38e77132472cc23f703aea9ede0d5ad","datavalue":{"value":{"entity-type":"item","numeric-id":5175965,"id":"Q5175965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$440561A0-DDFA-42E2-BC90-0B0F6AD3D292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f54afa2a3485ddcdc52058e1321b340acec88d76","datavalue":{"value":{"entity-type":"item","numeric-id":5928870,"id":"Q5928870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$050B1C8A-65AB-42BA-B1B5-CF7C275AA809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c31b0f2ce6c405b075a3e9e05cc7c4a2e32682ad","datavalue":{"value":{"entity-type":"item","numeric-id":4400851,"id":"Q4400851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$2DEEE349-BFE1-4CA3-BBD3-DF0418F5BAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"945c8511c11198e1a76a2127010852a7155b216f","datavalue":{"value":{"entity-type":"item","numeric-id":4312222,"id":"Q4312222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$2CF1BEF8-2F41-4AE2-93CD-688B44EA3331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$5CAB78AD-56CC-4669-BE76-865F4ABFEB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"420d293aed2d3d9d502aa06a5f320db4d977f0c8","datavalue":{"value":{"entity-type":"item","numeric-id":4517129,"id":"Q4517129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$F85B7190-6F04-42A2-8BF1-9142797FD40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd94578b97c83ef7077e73a3f78c579ae10dd88b","datavalue":{"value":{"entity-type":"item","numeric-id":3826599,"id":"Q3826599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$894DA72A-90DC-45C2-85AD-3DF504BE4F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b808bb57740e05faa3e8a9c198630a5e8fb4cce4","datavalue":{"value":{"entity-type":"item","numeric-id":4730798,"id":"Q4730798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$79DC04C6-705C-46BE-977B-447F2E0F95F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99a687c6a7f331ae64190b173721bd6d605a6aff","datavalue":{"value":{"entity-type":"item","numeric-id":3797204,"id":"Q3797204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557826$7368FB7C-B618-45A4-BD0A-A7E217A188B7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f13ae89f594c092db8b720210c2e5a215a9218d6","datavalue":{"value":"10.1016/J.TCS.2004.11.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557826$803000CD-F3F4-4657-8695-17B22D5A9B0D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"185eebca01652bce188f9e90087fdf79c33c0d26","datavalue":{"value":{"entity-type":"item","numeric-id":4537738,"id":"Q4537738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74a54c44084814da26f86d9833caf5e9bb34b757","datavalue":{"value":{"amount":"+0.8842011094093323","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":"Q557826$FAED4BD1-9841-4355-B4DC-4D3B09A413C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27af89a67206568d37ce23f155720cf819aa947b","datavalue":{"value":{"entity-type":"item","numeric-id":4312222,"id":"Q4312222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f18e1ef94bc6c2e5542463cfe9243d2ccd12009a","datavalue":{"value":{"amount":"+0.8838589787483215","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":"Q557826$AC1D0734-DC85-4A27-B10C-7C9806F089F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af75b6afda85300d16ada867a8b568dbbdccc094","datavalue":{"value":{"entity-type":"item","numeric-id":2754183,"id":"Q2754183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636f6c5a1244bda566d34b2399e662ec92679378","datavalue":{"value":{"amount":"+0.8752941489219666","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":"Q557826$E6050CFB-6A8E-43EC-BFA4-4875942013D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e71576123f91fd9232c02f518f9a68a6c2e08c7","datavalue":{"value":{"entity-type":"item","numeric-id":4210117,"id":"Q4210117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636f6c5a1244bda566d34b2399e662ec92679378","datavalue":{"value":{"amount":"+0.8752941489219666","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":"Q557826$83999774-28A6-4B52-BB0A-2A974F94E9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90876871508cef1044024e7534023a4b74d1ca0d","datavalue":{"value":{"entity-type":"item","numeric-id":5945922,"id":"Q5945922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"332511a620359756f70c1187326bd56f34066fd4","datavalue":{"value":{"amount":"+0.8713036179542542","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":"Q557826$80903003-0B30-42B1-A97F-BA7BF649B0B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:557826","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:557826"}}}}}