{"entities":{"Q4907576":{"pageid":6937155,"ns":120,"title":"Item:Q4907576","lastrevid":51648866,"modified":"2026-01-19T06:20:28Z","type":"item","id":"Q4907576","labels":{"en":{"language":"en","value":"An \\(O(\\log^2{k})\\)-approximation algorithm for the \\(k\\)-vertex connected spanning subgraph problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6134254"}},"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":"Q4907576$DADA6BAE-9D26-4810-AD16-D50B6A947746","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c46a87d0e583b67b2a131b6131b895d90fafb1b6","datavalue":{"value":{"text":"An $O(\\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4907576$9A000AA1-B7F6-4567-ABE2-52EF7292AAA8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7d2116f559477204e6bdcc47557f0aa0f14610c9","datavalue":{"value":"1257.68147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$8A3355F5-AA5E-4573-BB18-034E4A5D3ACF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5197a8df71e23613dda216ae364d50dfddef8481","datavalue":{"value":"10.1137/110855910","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$3F629559-308C-4CE4-AD11-AB00FA3BA7AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6812be559cce2a953030334367ce50b0349f7122","datavalue":{"value":{"entity-type":"item","numeric-id":509881,"id":"Q509881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4907576$CFF4E755-5A43-41A9-BE88-238E3DFBA294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"433e640f4acbffdd1fef3f2b4ef3fe5a14204f1f","datavalue":{"value":{"entity-type":"item","numeric-id":487014,"id":"Q487014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4907576$F0C0B822-476E-4DB9-9367-A2097A53A295","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4907576$7EF92376-6EAA-4BDF-86F1-D57BBDDB983B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3303370592b590ea2daf77b34dbd2db9a539c4a2","datavalue":{"value":{"time":"+2013-02-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4907576$6FAA4E3A-2A2B-4B96-95D2-CE9CAC34EB71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$D9FCD68D-A70D-4FF1-AF5C-9C7F62E79220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$A1CFA22C-4260-41DE-AAF8-CDA7A6EC6A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$C09FA8B6-F648-4C74-8584-CEFED1B88871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$4D83DA4D-834F-4946-A38F-9384D1E62D60","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"abda4110dbe8536c889d16096894fdd9aa4cbf27","datavalue":{"value":"6134254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$0606A48E-01E8-4367-B5F8-FCD600C31FE0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4907576$27075243-20BF-42EB-AEC6-8CA8C628CE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2c29e75b78ce20dab786a5fe8dd89da1ca64795","datavalue":{"value":"connected spanning subgraph problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4907576$C3A53AF8-210E-4E06-BDCA-8613E91846B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9b840116684b981cd835fcd471932d6ff35858","datavalue":{"value":"Frank-Tardos algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4907576$FEA5C12A-A6E8-4A33-BDC8-E426E0BFFD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f81e89c98df38265c4d3dece6b6c7001392b85fb","datavalue":{"value":"\\(k\\)-outconnected subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4907576$270A70D6-D584-4954-A8DC-67933A8FA7FD","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":"Q4907576$6E1E0E70-60B3-49B1-90B5-DA6804B1EF67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"652d7a79bf3944064a83a9c6f1337e99aa2e18f4","datavalue":{"value":"https://doi.org/10.1137/110855910","type":"string"},"datatype":"url"},"type":"statement","id":"Q4907576$DB562D89-B7A1-4CD9-AB89-FBE2981CD98F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae54d08a607d2f4ffa00f15559167a6914b583b8","datavalue":{"value":"W2058521212","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4907576$18758A6C-8F7E-4852-9BA1-B2E9B2511D59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c39fbb89b1d3709023622cf2a9a4ccbafbcf3006","datavalue":{"value":{"entity-type":"item","numeric-id":4429672,"id":"Q4429672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73097c58664d454af115c44f6a8f27e1c1bfcf23","datavalue":{"value":{"amount":"+0.926076352596283","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":"Q4907576$DA514E17-1BF2-47B2-91D7-D84A1D2C77EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c5a70f5b5402ad2f2a1b9c943e155fafe31d6ce","datavalue":{"value":{"entity-type":"item","numeric-id":4719338,"id":"Q4719338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"587b0d3659632606a382e3d5e93e82ee8c4dfd9c","datavalue":{"value":{"amount":"+0.8799142241477966","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":"Q4907576$58D27493-8949-4273-89EE-29137F828C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3217aec1e191bdcf224d868e7653ce5aaabebcae","datavalue":{"value":{"entity-type":"item","numeric-id":494800,"id":"Q494800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8d9e9bf647b76027ae1fb808e20997dbfaef17c","datavalue":{"value":{"amount":"+0.8790698051452637","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":"Q4907576$E6FFA214-3CF1-4DE5-9B95-8314E86EBDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c41e5bb7b05f82b873c845f2cc9515befeb0476","datavalue":{"value":{"entity-type":"item","numeric-id":4719339,"id":"Q4719339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9931ad3a1a3831da678c526de004911b3ce4359","datavalue":{"value":{"amount":"+0.8669219017028809","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":"Q4907576$A103F203-3B2A-4D68-AE65-A18754DF41C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80b869fa7ae0749839a98023248ca89296380968","datavalue":{"value":{"entity-type":"item","numeric-id":3580964,"id":"Q3580964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b097aad7a09a1c2d764c098b3819835b6e307d4d","datavalue":{"value":{"amount":"+0.8668085336685181","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":"Q4907576$9DB04ACB-4F74-49A2-8149-22F1D57F3A7D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4907576","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4907576"}}}}}