{"entities":{"Q2706198":{"pageid":2716937,"ns":120,"title":"Item:Q2706198","lastrevid":47587948,"modified":"2026-01-02T03:57:21Z","type":"item","id":"Q2706198","labels":{"en":{"language":"en","value":"Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1578830"}},"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":"Q2706198$B5F52135-97E1-43E7-9F35-B4AEE70C5250","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55c7ae1d4b2d82a70898713098dd364b7c8a681b","datavalue":{"value":"0972.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$FD3D0A38-2486-4364-BA2B-2C715AA68212","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e349fdfedac9f99095f17946057621ce393b272e","datavalue":{"value":"10.1137/S0895480199362071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$537F4D5F-596A-45EF-9A86-00E457F9B23C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2e2fd632e23324e356d8ca97c2e98ef9898398c","datavalue":{"value":{"entity-type":"item","numeric-id":210363,"id":"Q210363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706198$0634BEC6-9B69-4ACC-B77C-17EFF612F08B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a4895db1da1fd9aed91d3d4f5cc26a3bd76d976","datavalue":{"value":{"entity-type":"item","numeric-id":210158,"id":"Q210158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706198$8A8E2325-1563-4A57-BBA3-B01321871D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3e27675af97cbeffb3f1389b25a0aa71626fc15","datavalue":{"value":{"entity-type":"item","numeric-id":294661,"id":"Q294661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706198$4026650E-7BE8-4B4E-8F99-87005C7EF214","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706198$F53B9FE0-8122-46C2-BF66-9F46718C3126","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0da0ddb63369ee51f0c4f965ee150089663821f4","datavalue":{"value":{"time":"+2001-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2706198$E1966030-A090-40AE-B1BF-06AF29EFA1C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$DDBE4754-E8F2-4B7C-8788-91402F69FA4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$CC13910C-2E22-43E3-91D0-73D8FC239DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$1336598C-ADDC-4A87-A821-59BE6D36363E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$04119436-5003-4499-9B2A-1AA668A0582D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$62616B2D-F94A-4A6E-AE36-CEBCFF96A05C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3f18245130f7a2a794c14bee01e200afa5b29e7","datavalue":{"value":"1578830","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2706198$B87C2944-817B-4818-95DD-C2AC426B645F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a98fdc415b871902bf310caee2992f6f1b91c39","datavalue":{"value":"travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$33DCB6C4-7847-4D88-BFD6-071BAC755AD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$C231462B-BC82-4AD0-8AE7-B7A37D22991C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$A654A26C-E32C-4641-AE67-F0432BDEC5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09991e4d9c4630e665aa8d5f02c4d7920d174564","datavalue":{"value":"ear-decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$4283D686-519D-48A0-80F5-BF4124A4CACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"852bfa6cfdd4b5184c268b667b3ff1c03b5ffa86","datavalue":{"value":"2-edge-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$580377D3-5CBD-46B9-973B-002719E7A141","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":"Q2706198$C74AE9E4-24E2-415C-A76F-1958FFA082BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"620f8bdecba008fd74ce451511eb47fab0ac049a","datavalue":{"value":{"text":"Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2706198$728BF545-6C01-4E60-8490-FE874489F134","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c315e98a5f82f8f28ec2dc7f905eb8b2eb442e65","datavalue":{"value":"Finding a minimum size spanning 2-edge-connected subgraph in a 2-edge-connected graph is NP-hard as the Hamiltonian cycle problem is a special case of this problem. It is easy to find a spanning 2-edge-connected subgraph with no more than twice the optimum number of edges: simply find an ear-decomposition of \\(G\\) and leave out all the trivial ears (those that are just an edge). Khuller and Vishkin gave a 1.5-approximation algorithm for the problem based on depth-first search. In the current paper the authors give a \\({17\\over 12}\\)-approximation algorithm for the problem based on a result of A. Frank on the minimum number of even ears in an ear-decomposition of a 2-edge-connected graph. Recently Vempala and Vetta have improved the best approximation guarantee to \\({4\\over 3}\\) [\\textit{S. Vempala} and \\textit{A. Vetta}, Factor \\({4\\over 3}\\) approximations for minimum 2-connected subgraphs, in Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Max-Plank-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany; Springer, Berlin, 262-273 (2000)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2706198$8B672871-93BE-43D2-802D-5AF5F390485E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2706198$A8C6FEE7-A1FD-42C9-89B7-3534955677EA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"792b3361efe17f46670735ff2e5aeecd09624235","datavalue":{"value":{"entity-type":"item","numeric-id":3840352,"id":"Q3840352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bf63c7fab75a5a3d14ec1969fbc7538da460e7d","datavalue":{"value":{"amount":"+0.9116954803466796","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":"Q2706198$5DD7DE89-C50C-417F-B6A5-B36D000A753A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b15c5d0a54de31348b7768af4fe043889212f68","datavalue":{"value":{"entity-type":"item","numeric-id":1426722,"id":"Q1426722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d347823b666edf327d984832603dd4eb82ea11","datavalue":{"value":{"amount":"+0.881896436214447","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":"Q2706198$84EA5C59-0A5F-4EAE-9123-B0BA00AF80B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86a138bf67b4d0463a1cba7a231536d325134bed","datavalue":{"value":{"entity-type":"item","numeric-id":4973051,"id":"Q4973051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91042f4be543d8ee209ed7996752b5eceeb38762","datavalue":{"value":{"amount":"+0.8799753189086914","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":"Q2706198$C2AB89AD-CEDF-4448-A13A-3270A9D6CC91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a230e12ee278dae228eb2d3b4e0d125abfac108","datavalue":{"value":{"entity-type":"item","numeric-id":4299007,"id":"Q4299007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4475c368f58d5e3759df50b75eea3b0fe1f8cc7c","datavalue":{"value":{"amount":"+0.8767139911651611","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":"Q2706198$3E6D392B-3A86-4AAD-9F23-2891DCBE5103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c41bf310702f615d24b06a293c5d83b0ab81da06","datavalue":{"value":{"entity-type":"item","numeric-id":1861569,"id":"Q1861569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4475c368f58d5e3759df50b75eea3b0fe1f8cc7c","datavalue":{"value":{"amount":"+0.8767139911651611","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":"Q2706198$6D828DFE-B57B-43AD-A8D9-CCBC7AD675CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2706198","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2706198"}}}}}