{"entities":{"Q1422410":{"pageid":1433150,"ns":120,"title":"Item:Q1422410","lastrevid":71871585,"modified":"2026-04-14T01:05:49Z","type":"item","id":"Q1422410","labels":{"en":{"language":"en","value":"Splitting off edges between two subsets preserving the edge-connectivity of the graph."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2041892"}},"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":"Q1422410$E54BA080-2AB3-494E-825D-7ABCAC25ED4C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e570af8a1ffe16e3075ca5f9c31eb0b854e316a1","datavalue":{"value":{"text":"Splitting off edges between two subsets preserving the edge-connectivity of the graph.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1422410$A5564D17-F333-4CCA-8B8C-EC74047C6962","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7272e7d5daea740d7c9155da9e671a05713907ba","datavalue":{"value":"1039.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$5CC237D6-AF04-4489-9011-49F910927AF1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a86e826c4d3e705f462db8512ba4ca5ebbea0124","datavalue":{"value":"10.1016/S0012-365X(03)00291-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$542C27A4-6321-48F0-BAE8-10CFE7225E27","rank":"normal"}],"P16":[{"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":"Q1422410$3BFF3B92-1F84-4E78-952E-44B2C4B991EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f64c4b091272c660c279938fc740575735afef58","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$32FF6B70-4825-4552-A610-FAF76F765DBF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$F44E8060-9D90-4C94-9E59-B3F03F4ABC58","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1aee94454bbb3bb990b95de2d91d20cd9c9645ff","datavalue":{"value":{"time":"+2004-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1422410$D8919970-344A-445B-A2E9-A3FA5D4AB141","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4793c7d864c0d1b82ce897d3ec83bebf16635214","datavalue":{"value":"Splitting off a pair of edges \\(su\\), \\(sv\\) in a graph means replacing these two edges by a new edge \\(uv\\). Let \\(G=(V+s,E)\\) be a graph which is \\(k\\)-edge connected in \\(V\\) (i.e., there are at least \\(k\\) edge-disjoint paths between every pair of vertices of \\(V\\)) and suppose that the degree of \\(s\\) is even. \\textit{L. Lov\u00e1sz} [Combinatorial problems and exercises (North-Holland, Amsterdam) (1993; Zbl 0785.05001)] proved that if \\(k\\geq 2\\) then the edges incident with \\(s\\) can be split off in pairs preserving the \\(k\\)-edge connectivity in \\(V\\).  In the paper under review, the authors study the following \\((R,Q)\\)-split completion problem: given a graph \\(G=(V+s,E)\\) which is \\(k\\)-edge connected in \\(V\\), disjoint subsets \\(R\\), \\(Q\\) of \\(V\\) and an integer \\(k\\geq2\\), find a minimum cardinality set \\(F\\) of new edges incident with \\(s\\) such that in the new graph \\(G+F\\), all edges incident with \\(s\\) can be split off preserving the \\(k\\)-edge connectivity in \\(V\\) where every edge from \\(s\\) to \\(R\\) in \\(G\\) is split off with an edge from \\(s\\) to \\(Q\\).  First, the problem of finding the longest possible sequence of ``admissible \\((R,Q)\\)-splits'' is solved. The length of such a sequence is characterized by certain ``obstacles'', i.e., substructures of \\(G\\) which preclude the existence of long admissible \\((R,Q)\\)-splitting sequences. An algorithm to find a longest sequence is given. Then this algorithm is used iteratively to solve the \\((R,Q)\\)-split completion problem when \\(k\\) is even. For odd \\(k\\), an almost optimal (at most two edges more than the optimum) solution is found.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422410$E27A09A7-20B4-4729-AE45-C239987452CA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6dbc03ded8dc8f343dbb91f0750fa930e4a14011","datavalue":{"value":{"entity-type":"item","numeric-id":205838,"id":"Q205838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$E4B64522-8D8B-4C77-B1FC-F96FA47DAFD8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$545F012B-0DC9-4935-980B-3CF3E34C3087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$43295C92-687E-4873-8BD5-ED891375B3A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1941d1101659c3e27efed2468dfa9b6c2c85fa3a","datavalue":{"value":"2041892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$1EDBA49F-FC9B-4252-A967-A40B19B1D810","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a19673f7efd5bc6bcf2de877cd1a8895efec9379","datavalue":{"value":"edge-connectivity augmentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422410$058FD518-3194-47D7-8FDA-5A4EDD273C39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6518744e88d7d8cb3f062f1928adfe74deced0fe","datavalue":{"value":"split completion problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422410$03831550-59C0-4AA7-9C08-32781F60F313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbc6d8d1b8fb18ca87ceabc0565ca1b85d922961","datavalue":{"value":"partition constrained augmentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422410$A40D9836-6643-4527-83F5-0368E7386E61","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":"Q1422410$0CDEEF21-C604-4616-8124-AFD03638526B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83bfb8cd61a6cd4a446c69da0163b606c4f6418","datavalue":{"value":{"entity-type":"item","numeric-id":4837644,"id":"Q4837644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$7B094B3B-32FC-4D99-AE5C-2919B76DCEFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f236e1be2ac94c7745f28a2b330e1da8c734111","datavalue":{"value":{"entity-type":"item","numeric-id":4255815,"id":"Q4255815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$18911182-5BAA-49FE-AE4C-0584D729B289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1081639c735f98cc27baa5fce8aea649cd6cb182","datavalue":{"value":{"entity-type":"item","numeric-id":4210226,"id":"Q4210226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$9B6B4499-BADA-45A9-A464-5D69A1B80EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90ed7c0a9f29be7f582b57e1941cf3217974d29f","datavalue":{"value":{"entity-type":"item","numeric-id":4521519,"id":"Q4521519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$923AA348-AAF1-4E66-96B3-B72F9759D6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b67fe127ea64dfc69c3ace11f8c7804c6928784","datavalue":{"value":{"entity-type":"item","numeric-id":3825104,"id":"Q3825104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$7578ABCC-30A4-4FD2-964D-1526CF8694F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28ca4612abeb81058a52230732f37d3e03995d8a","datavalue":{"value":{"entity-type":"item","numeric-id":3828033,"id":"Q3828033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$F46C5CE0-2DF0-4DAA-B881-FA2D3EBD0449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff4f3e0736459225ac2e4084da2fef9d84c767fc","datavalue":{"value":{"entity-type":"item","numeric-id":3989009,"id":"Q3989009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$48979B0D-6B76-4594-A305-01B328B331D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd633005b9ed0b459a1d00251c97e75a253b406f","datavalue":{"value":{"entity-type":"item","numeric-id":4845372,"id":"Q4845372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$8222BAA3-4981-4FF3-817C-8B64C529C487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"759fdcac79b9a44582453742844da0caa96f5fcc","datavalue":{"value":{"entity-type":"item","numeric-id":3794218,"id":"Q3794218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$C1A8D6FA-C3EE-4B6A-9170-618BDF392102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$E6AF7E7D-3035-42E3-8186-73BA770B38F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8043dd107c7904927ab042bfc394b0b4d1ce82c4","datavalue":{"value":{"entity-type":"item","numeric-id":4170751,"id":"Q4170751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$ACBCECD0-6377-4118-AAED-BAD4E2CD7012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c15ea52aba9e8d7cd3207e872f8306cce77e3f6","datavalue":{"value":{"entity-type":"item","numeric-id":1165861,"id":"Q1165861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$D3452305-6146-4AD1-8310-BB15BB381B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bfec4e8ad12cf4cf193288ede245783106c2566","datavalue":{"value":{"entity-type":"item","numeric-id":3840350,"id":"Q3840350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422410$6C7BA19F-8B43-4D75-B56A-793AD7C80EEF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f63112d8d05c2fd7cdfd2642b43abed9b71bcc2b","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(03)00291-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422410$448EA8F5-4A2F-4D2F-ADD5-A35F04274166","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a8c82bbf1a2c1fbbcd78c56524c939cc6affbbf","datavalue":{"value":"W2058149194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422410$4F4776CE-0D6F-478A-9F2E-CEDC19276959","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d5d0ed88fcbbd7075490f0304dc9245b4e62689","datavalue":{"value":{"entity-type":"item","numeric-id":4521519,"id":"Q4521519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48ed926f875dafd945628f8d74a86a7acf8b9dc3","datavalue":{"value":{"amount":"+0.9498484134674072","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":"Q1422410$BAD6389C-1BD4-4162-930B-D167B28069D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b26d9c166e3d503e44fe2e326a18eb000fcc2ab","datavalue":{"value":{"entity-type":"item","numeric-id":3840350,"id":"Q3840350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"671ad0583cc978205cc168fed020c7a7f8bed887","datavalue":{"value":{"amount":"+0.949375331401825","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":"Q1422410$7E533DC3-B9F9-490D-AA4D-2D11F435C40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfd94c1519fceadedcf504af7cdebc7ae5a4321d","datavalue":{"value":{"entity-type":"item","numeric-id":4443123,"id":"Q4443123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c87c62130587eb3213575ce013669cfb6a614a78","datavalue":{"value":{"amount":"+0.899511992931366","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":"Q1422410$956663DA-287B-4EB8-854A-A787430C8CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eaa959cfb11ebd3e95c9e296e383dcaf26de3f7","datavalue":{"value":{"entity-type":"item","numeric-id":1402535,"id":"Q1402535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e34b48c762c368803476efeb81b4bbad8b2d688","datavalue":{"value":{"amount":"+0.8990753889083862","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":"Q1422410$28DA3D9E-964D-40AF-B321-E655E79AE669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5f28731fb20629c63de51dc656df192a3f9ab1e","datavalue":{"value":{"entity-type":"item","numeric-id":4263718,"id":"Q4263718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1713b840640bfba111a298c714a9e0fbcba0fdf8","datavalue":{"value":{"amount":"+0.8963326215744019","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":"Q1422410$44C2D0DD-8E07-421E-94D6-7090A0558233","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Splitting off edges between two subsets preserving the edge-connectivity of the graph.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Splitting_off_edges_between_two_subsets_preserving_the_edge-connectivity_of_the_graph."}}}}}