{"entities":{"Q997070":{"pageid":998918,"ns":120,"title":"Item:Q997070","lastrevid":65919414,"modified":"2026-04-12T06:16:07Z","type":"item","id":"Q997070","labels":{"en":{"language":"en","value":"Bisecting a 4-connected graph with three resource sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5173159"}},"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":"Q997070$5991FFF3-9FA1-45C9-84B0-A86184D8B059","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c8efeecf3c28d16b93cf2760f657606c8a002fc","datavalue":{"value":{"text":"Bisecting a 4-connected graph with three resource sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q997070$545E4929-69C5-4AC3-B73C-00835291468D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ae72f640d329ff8ae3647a9dd1ab250eede3f4a","datavalue":{"value":"1142.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$049C83C6-A980-4768-BCF1-A80C49A61162","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd50cafeb7b40aba5852fdface8d2050ee59a85b","datavalue":{"value":{"entity-type":"item","numeric-id":290103,"id":"Q290103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$B41064A2-8281-4CB5-AF61-3A328A7568CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35714bbcfb6f70c675344fa96ffbdbc7879363ae","datavalue":{"value":{"entity-type":"item","numeric-id":997069,"id":"Q997069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$B09719FC-7975-45B2-8231-4C0E46436719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"60eb2392c3cbb67419a7505eb4d7770437782b61","datavalue":{"value":{"entity-type":"item","numeric-id":187130,"id":"Q187130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$AC8DA039-89D3-4C5C-896D-8D67B3E81510","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$4C6179CD-9F82-46D8-888A-71C8AE486411","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"227f49044efd7c327d9fee9eb29461e125a6d477","datavalue":{"value":{"time":"+2007-07-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":"Q997070$7CB01EE1-B2BD-4BF5-9414-9C187B821556","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0169042ad49ee14fc69f38341b74a1d13ccb181c","datavalue":{"value":"https://barrel.repo.nii.ac.jp/?action=repository_action_common_download&item_id=49&item_no=1&attribute_id=19&file_no=1","type":"string"},"datatype":"url"},"type":"statement","id":"Q997070$74002847-D1EC-4019-A8A9-F4B0C08165AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d3bcc343ecbaa1fc9a27b7dd32185f7c2ce1c3e2","datavalue":{"value":"Let \\(G=(V,E)\\) be an undirected graph and let \\(T_1,T_2,\\ldots,T_k\\) be pairwise disjoint subsets of \\(V\\) such that \\(| T_i| \\) is even, for \\(i=1,2,\\ldots,k\\). A partition of \\(V\\) into two subsets \\(V_1\\) and \\(V_2\\) such that the graphs induced in \\(G\\) by \\(V_1\\) and \\(V_2\\) are connected and \\(| V_1\\cap T_i| =| V_2\\cap T_i| =\\frac{| T_i| }{2}\\), for \\(i=1,2,\\ldots,k\\), is called a \\(k\\)-bisection of \\(G\\). It is known that every \\((k+1)\\)-connected graph admits a \\(k\\)-bisection for \\(k=1,2\\) and it was conjectured that every \\((k+1)\\)-connected graph admits a \\(k\\)-bisection for \\(k\\geq 3\\) as well.   The authors disprove this conjecture for \\(k=3\\) but show that a \\(4\\)-connected graph \\(G\\) admits a \\(3\\)-bisection if we additionally assume that \\(G\\) contains a copy of \\(K_4\\) as its subgraph. Moreover, they give an algorithm constructing such a \\(3\\)-bisection working in time \\(O(| V| ^3\\text{log} | V| )\\). They also show that for an arc version of the problem \\((k+1)\\)-edge connectivity suffices for \\(k=1,2,3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q997070$9D4A7AE9-2EB7-4A04-8648-2D8757943899","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$28F2A287-186A-4604-B84D-9C45416F85B4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$CC5A66D1-0C14-44D7-912E-C4F3019F12A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$E0C72183-1B9F-4B2B-9AA1-139C9EEC2ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$372E7F4A-2E80-40DB-8E56-24D52A9C5BB9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba2f6f79820bf13d06ccd6454947c8de0555155b","datavalue":{"value":"5173159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$25585485-C9C0-4908-8D36-638F79134B9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51a4d2f184eb71178bc677bcea7c20cd074b818c","datavalue":{"value":"graph partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q997070$279B4FD6-DC0B-4EAB-85AB-1670ED3BBAF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ba9eef800f70aedd4479c95aec2fd7d3c9fb7d7","datavalue":{"value":"graph bisection","type":"string"},"datatype":"string"},"type":"statement","id":"Q997070$9CF34DF3-C806-48BA-8CE6-DCB927CA14F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"942090a43c9689eb1ec56ea5d49e20aceb30d1c0","datavalue":{"value":"graph connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q997070$27D8E567-F031-4102-8103-0C939E498440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q997070$5FC321C8-9ABB-42A7-BA7E-EE8271100904","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":"Q997070$AF42985B-A653-4103-A063-84AFF82438E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00b279c688c1af4d7c9a82b772860b87a0a39adb","datavalue":{"value":"W2154818280","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$2E5D4B54-8A83-4464-BFDD-30B806F6C129","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e459408e80face6ea829385677173d2b18d247a8","datavalue":{"value":{"entity-type":"item","numeric-id":1869686,"id":"Q1869686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$684BB0CC-1022-419A-BF52-115B7E53F564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5120308fc224bc7a8814cdec5e9ffd530b355a2b","datavalue":{"value":{"entity-type":"item","numeric-id":1329191,"id":"Q1329191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$72316025-2027-4EE8-BBD8-1F2B9F0D7C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6b46a9df1f58bdf853a0f322b0c3106df9cffcd","datavalue":{"value":{"entity-type":"item","numeric-id":673224,"id":"Q673224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$BE84B7D0-B212-474A-8915-9E57249F3EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4e3ae15161a37724dad1b7932a94d4c31fc0c7e","datavalue":{"value":{"entity-type":"item","numeric-id":1057062,"id":"Q1057062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$36BAAA34-D938-4E45-8418-1A3AC5E73ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$80CD08CD-B0B0-49A8-9B4D-E301149ACA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"278084b8673d303cd2d9271ea24976c055f370d5","datavalue":{"value":{"entity-type":"item","numeric-id":3883550,"id":"Q3883550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$FE755B34-3FA4-4D98-AF52-80F08CFAEE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6aae86ad2bc3705bd0ca216355e1b98ede0a986","datavalue":{"value":{"entity-type":"item","numeric-id":2277470,"id":"Q2277470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$DBC40C03-6CAA-4D7F-A23E-EB20F56F53BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d99b4366655c3c9c674922ff78c44c9ecd0c17d3","datavalue":{"value":{"entity-type":"item","numeric-id":1186788,"id":"Q1186788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$5D1CBC22-256C-4A78-A4A1-5096B64C8064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"622b71f227b4f9b022909fcaa9e5916fd13155a4","datavalue":{"value":{"entity-type":"item","numeric-id":1410408,"id":"Q1410408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$63269B9C-4439-49FB-9B34-583B4210E02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b173cf23638ed0234267370852798d4daae5dc0","datavalue":{"value":{"entity-type":"item","numeric-id":911298,"id":"Q911298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q997070$4B4E44CE-EDAB-4824-85A7-4AF11B720330","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45dda814a20dc5d858127c2c7b0ed1b4f037a826","datavalue":{"value":"10.1016/J.DAM.2007.03.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q997070$7B33CBC7-C9B0-4DD4-B7EE-55D9241C6BF6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9ec87dfa6f4edcbf7bc185eef940b699be289ef","datavalue":{"value":{"entity-type":"item","numeric-id":5897851,"id":"Q5897851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5918cb07b5111c89cc4f7c38f3c46b48f8f435dc","datavalue":{"value":{"amount":"+0.9469794631004332","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":"Q997070$C2BE0C95-3F68-483E-A9AA-2DFAF2BAF460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3003557da651899eb46ecdb25ac13586b34be260","datavalue":{"value":{"entity-type":"item","numeric-id":4511243,"id":"Q4511243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"464aebec7ec345786cf13b49bbda2e3f15c15108","datavalue":{"value":{"amount":"+0.8595184087753296","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":"Q997070$F5A7A5B0-D3FA-438F-B8F4-024ADA479F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60430acb9eea0ab0a4b1ed373f8842b548f24920","datavalue":{"value":{"entity-type":"item","numeric-id":1730254,"id":"Q1730254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6e48a6d9fd99031aeeaf0f25f2ddc0ff1c33859","datavalue":{"value":{"amount":"+0.8578663468360901","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":"Q997070$5BD7B775-95A8-4DB4-95AC-47655255247C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"781781b9fd098ec4ffa7c2fc4e58763880c38d13","datavalue":{"value":{"entity-type":"item","numeric-id":2566018,"id":"Q2566018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ec1fae3118530ab7c71fa4f9ba8e78a19aeab37","datavalue":{"value":{"amount":"+0.8283897638320923","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":"Q997070$5EE1659A-A99F-4D90-A0BF-D46C7FDA5F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c7318b7310cfae85574c691714ed1bc6cf432b","datavalue":{"value":{"entity-type":"item","numeric-id":1410408,"id":"Q1410408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ce0f86a379b836001d6d4346ee56b70076b6acb","datavalue":{"value":{"amount":"+0.8207096457481384","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":"Q997070$A2E768C1-2D9C-4D41-8A25-0749F9899989","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bisecting a 4-connected graph with three resource sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bisecting_a_4-connected_graph_with_three_resource_sets"}}}}}