{"entities":{"Q1300062":{"pageid":1310812,"ns":120,"title":"Item:Q1300062","lastrevid":70096479,"modified":"2026-04-13T12:24:57Z","type":"item","id":"Q1300062","labels":{"en":{"language":"en","value":"Successive edge-connectivity augmentation problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1332946"}},"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":"Q1300062$3D2CC113-7672-4BCE-9E54-19905CA4049A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee767f5007d4823d85b1f431daffc70003b6c5bd","datavalue":{"value":{"text":"Successive edge-connectivity augmentation problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1300062$D11B0D19-046B-4738-82AE-FB7FFE5ACC62","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f57b58778ee656731001311ac68c0e64e94318b","datavalue":{"value":"0939.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$928452EA-4C00-40D4-B91A-58BCD5399F8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b53da2f6174cf6e1dd6d58e8e37b2209648a75ed","datavalue":{"value":{"entity-type":"item","numeric-id":294706,"id":"Q294706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300062$C227170A-A257-4575-BBD3-5EF765B0195E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"720a2470955600a0e199ea4312c70a5e6b991176","datavalue":{"value":{"entity-type":"item","numeric-id":226798,"id":"Q226798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300062$AFF2FD15-3D1D-4A14-90C2-93B3472BE110","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300062$BD0F1C95-B3C6-4801-8A89-788E4BAD00F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73a06eda8b8bc24f111c81307fdc67b9314f5da0","datavalue":{"value":{"time":"+2000-07-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1300062$92E78D85-2818-48D5-B4F5-0C3D9CF15C29","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"680ceaab6b2db280260c2362987e1c8549b01606","datavalue":{"value":"It was shown in \\textit{D. Naor}, \\textit{D. Gusfield} and \\textit{C. Martel} [A fast algorithm for optimally increasing the edge-connectivity, Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 698-707 (1990); and SIAM J. Comput. 26, No. 4, 1139-1165 (1997; Zbl 0884.05082)] that the so-called successive augmentation property holds for undirected edge-connectivity with uniform demands. That is, for any starting \\(G\\) which has edge-connectivity \\(l\\) there exists a sequence \\(G= G_0,G_1,G_2,\\dots\\) of supergraphs of \\(G\\) such that \\(G_{i+1}\\) is a supergraph of \\(G_i\\) and \\(G_i\\) is an optimal \\((l+i)\\)-edge-connected augmentation of \\(G\\) for every \\(i\\geq 0\\). The authors show how to derive this result from a variant of Frank's edge-connectivity algorithm; see \\textit{A. Frank} [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5, No. 1, 25-53 (1992; Zbl 0782.05054)]. In fact they show that even a stronger version (involving certain non-uniform demands) holds.   The authors also show the analogous successive augmentation property holds for directed arc-connectivity augmentations. Finally, they give examples to show that the successive augmentation property does not hold for any of the following possible extensions: hypergraphs, arbitrary non-uniform demands, vertex-connectivity of digraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300062$93CBBA2A-E5DA-44FF-B491-8B84A3A8FCAF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$8E47670A-EFD1-4332-8563-0ADFFC6C3F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$99898B5D-1C7F-4001-A5FF-EC66BB11A050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$73AA98BF-FCF7-40F9-BF60-3A695B9984FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54aa5eea4b5b90589cd456102303c14c5d7efb6c","datavalue":{"value":"1332946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$A831E05A-1E68-4A04-8A07-6B2A91D62634","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fd86154c3ff0dec8dff3eed78fc8450ff628dc2","datavalue":{"value":"successive augmentation property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300062$E968E6FA-C8A9-43EA-835C-D40DB519E847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05a980a525b12505f622c048012814c8c5735bc0","datavalue":{"value":"edge-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300062$464D119C-817A-4F6B-B1C7-78A121E75F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d7fa12204e92e17ac5d0834ec9644bd446105e5","datavalue":{"value":"arc-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300062$BF5208E3-87A1-46A2-A78E-2AF80AC4A3A6","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":"Q1300062$654668B7-AA3F-46F6-AC2E-8C6343A8F248","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":"Q1300062$E3B9781E-EEEA-4A3F-94D2-EA39545D0DFF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7e86ca1c1de0d3626c384f49064d996c7e08227","datavalue":{"value":"https://doi.org/10.1007/s101070050041","type":"string"},"datatype":"url"},"type":"statement","id":"Q1300062$416339FA-A3C0-459E-A2D1-CB1E8B6EA65C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3daf85e0896174867a532ef13f95670607345407","datavalue":{"value":"W2116598440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$8302B8CA-8345-4803-B7D2-A36C45718A65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11c9e768dfc6ddb4032582ce77c35ad4fbe7f0d0","datavalue":{"value":"10.1007/S101070050041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300062$B8A176BD-C61A-46EB-BF0B-D7D584499985","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e1f6d3f03ac0e6fed8c35278654cf0a944fe01","datavalue":{"value":{"entity-type":"item","numeric-id":2971622,"id":"Q2971622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b4219aba70cb9a51a666b1b9592819cc19438e4","datavalue":{"value":{"amount":"+0.8401962","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$CAC1F960-176B-4FB6-AE0B-FB5008F5CF21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227e54671b4cf7c3ef74156e7660ad3e46e44a24","datavalue":{"value":{"entity-type":"item","numeric-id":2816106,"id":"Q2816106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87ecddefd4935afb72e621116745e36d00864824","datavalue":{"value":{"amount":"+0.82909113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$D2F49A2E-0539-4D14-AC02-4186F21E415D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff8550d753082c226e379b29790bef7a650b16d8","datavalue":{"value":{"entity-type":"item","numeric-id":4210226,"id":"Q4210226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b19ec498eccc62b29461a7c0a03712b9051d9c1","datavalue":{"value":{"amount":"+0.80995697","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$101948FF-B499-4A73-B3DB-EA7DFB216118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3f1524594528ea5410aa1919b33b2dd4eb1a965","datavalue":{"value":{"entity-type":"item","numeric-id":1300063,"id":"Q1300063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97f47fbf946aa3c28df79c2ce7b8e53b5fac10c7","datavalue":{"value":{"amount":"+0.8063694","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$2631CAD8-2E4F-4FE9-89BC-5FFC5A909071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"993c77b2db79c3a5916c61dd92d73389c95cc488","datavalue":{"value":{"entity-type":"item","numeric-id":4255815,"id":"Q4255815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7314674ea8e163300b101ac8166c269282002bb4","datavalue":{"value":{"amount":"+0.80128884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$9FA5A9C3-7D01-44DF-BB58-6470F8205198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db2386216c7f1db68b2b0da916c69905176c1682","datavalue":{"value":{"entity-type":"item","numeric-id":1300051,"id":"Q1300051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9004919baf8117df587f7188cdcbe4967ecae97f","datavalue":{"value":{"amount":"+0.7944982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$7D25257F-6DCE-4489-93B1-352BB67FAA16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f833e9b80612e575da742c59d710519de90f8112","datavalue":{"value":{"entity-type":"item","numeric-id":4256090,"id":"Q4256090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdeef337446f8fd8ebad9df36b5a289afa5e474c","datavalue":{"value":{"amount":"+0.7938413","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$B73144A9-166C-4D23-9F17-A51C72CE992F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2826ebf1b63d879fca432d9219cf1e6888f71c42","datavalue":{"value":{"entity-type":"item","numeric-id":3094939,"id":"Q3094939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d4b38fb93cb9ec2693fe6aaf95f509a12ad6dda","datavalue":{"value":{"amount":"+0.7920798","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$A577E56D-A18A-4757-BA43-AEE3E87C5DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"430a4bac7c220d3a5182dc48d4a62050f6e07c5c","datavalue":{"value":{"entity-type":"item","numeric-id":2875183,"id":"Q2875183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b155145ec34aa3e3e733b9fae821b993ed2d6623","datavalue":{"value":{"amount":"+0.7910757","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$736C7287-FB43-4C68-BF99-F477E6232EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32110ffc9013e2455abb13ade9dbde9c1a9f20c8","datavalue":{"value":{"entity-type":"item","numeric-id":4376163,"id":"Q4376163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79ca7b90e90ebe1cbd5c658caa7b139fdcf901ca","datavalue":{"value":{"amount":"+0.7905213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1300062$3D829B45-4131-4AA7-ABD0-3BB592CCF9A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Successive edge-connectivity augmentation problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Successive_edge-connectivity_augmentation_problems"}}}}}