{"entities":{"Q2464161":{"pageid":2474904,"ns":120,"title":"Item:Q2464161","lastrevid":57938721,"modified":"2026-04-03T04:14:11Z","type":"item","id":"Q2464161","labels":{"en":{"language":"en","value":"Decomposing Berge graphs and detecting balanced skew partitions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5219096"}},"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":"Q2464161$47127953-D925-404F-BC40-07D4528AAF7E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"813ac41435197ee8b2a3fe38ce3b454195717b9c","datavalue":{"value":{"text":"Decomposing Berge graphs and detecting balanced skew partitions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2464161$A3971F50-3EA7-4E19-80D3-85D05483BDD2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6404e86b835eda45b9432972b1de1c062457db69","datavalue":{"value":"1131.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$18879593-06CB-4687-98EC-BDA4C66E271D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba8963bf07877ded4133836acba07ecf77a509c7","datavalue":{"value":{"entity-type":"item","numeric-id":442236,"id":"Q442236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$D2CC4719-33F3-4B52-BBB7-74C0B9DBD76A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$E381B33B-0E5E-4B7A-9640-4040D9682E15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"faa4e2db889e78b8ad508b312ddd6133608474a0","datavalue":{"value":{"time":"+2007-12-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":"Q2464161$6DF2C185-E235-4BE1-B90A-706D6EFF5C94","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dfe30603a8391163e7e2bd5252628e70b5872148","datavalue":{"value":"https://arxiv.org/abs/1309.0680","type":"string"},"datatype":"url"},"type":"statement","id":"Q2464161$945D61E6-E7C3-4357-82FF-F30CFDE2DC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"adb312d4754624fb351af40fa129213362a7858a","datavalue":{"value":"https://arxiv.org/abs/1309.1960","type":"string"},"datatype":"url"},"type":"statement","id":"Q2464161$D4A6EE36-C675-4ECB-A678-1B4E053852CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bc2f4002e80d269be923acc5f1beec63fddd2071","datavalue":{"value":"A hole in a graph is an induced cycle of order at least 4. A Berge graph has no odd holes in either itself or its complement. The author shows that the problem of deciding whether a graph has a balanced skew partition is NP-hard, but gives an \\(O(n^9)\\)-time algorithm for the same problem restricted to Berge graphs. The algorithm is not constructive; it only certifies whether a graph has a balanced skew partition or not. It relies on a new decomposition theorem for Berge graphs, which also implies that every Berge graph can be decomposed first by using only balanced skew partitions and then by using only 2-joins.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$4EE40774-8D95-4665-A081-8E1EB15F1D99","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$A340FDE9-0EDC-4AC5-883C-1CB0F160755E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$866FCC55-65FF-4889-AF8D-537EA1D8AC11","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e9c71585aa9d861483bfef5eb7913d464c8592f3","datavalue":{"value":"5219096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$859182F2-420F-4CE4-AD19-5FDB5CAF5F9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$20494CF4-5B98-4E87-A9D9-4BADE4219042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5594bf089e20db614ce61dae32b887cd362d61e2","datavalue":{"value":"Berge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$10C3E432-7088-4948-8C19-B62B1807918A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b37812d7925d4374fc15b1ec0404a5d59f4d080","datavalue":{"value":"2-join","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$7919990C-ACC6-42E9-8605-490FB2CCE983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54a001d3a7788ce5ebe16336248cb1469a583849","datavalue":{"value":"balanced skew partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$DCD6C60C-A4B1-498E-B110-8ADAA39DF42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$705924A3-81F7-4F18-8016-F31BD0AC5D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb30ce01c7fef0458eec38b585a0ae613d7a304d","datavalue":{"value":"detection","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$8C38DB2C-DCB4-4210-BD75-71D7AD294671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9891227b3d7ca9f091fdc17473271d45c5e2f962","datavalue":{"value":"recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2464161$4AA6ACE0-72F2-45E1-93C1-C96ABC2089F1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$F648574A-8A2D-43E6-8D04-54FDEB229457","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":"Q2464161$7EF3017C-7BCB-4C32-8B37-958A04FA6233","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6b52ee770a0f356ab6c2f5165222b303a4a28bff","datavalue":{"value":"W2020405408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$04CCAA3A-D070-4DFF-A0E0-35F8E81A38E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$93D19327-5C90-4A43-94B2-8D9281D7117C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f57ee27c1e98893d8e31c050c36e8476a353c4","datavalue":{"value":{"entity-type":"item","numeric-id":5487777,"id":"Q5487777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$3D9C7677-0000-4E36-A307-AF9EB5F90CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$8E48457D-8ADA-4FB5-A23B-CCC5806DF344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$7E6BC8DD-EF0A-4572-9DD3-ED1E1AB0570A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$160AD511-04F5-4CE4-96F0-D5D50A4788D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f80bd66875089f385bc846e7e7f8ca82fdf2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$A63FAB80-604F-4BC9-B642-85724813BB43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40db7978f2fa4f72a9fc47f33a15ad28a0b78f1a","datavalue":{"value":{"entity-type":"item","numeric-id":3150171,"id":"Q3150171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$C51A1B33-BC08-4F33-A427-858968609ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da82e4f00cfc49b12605cd034d724465398c4f6d","datavalue":{"value":{"entity-type":"item","numeric-id":1426100,"id":"Q1426100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$AEBEE593-FBA2-47B2-8CAD-9D8A30EEE66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6a194d77b2283bcad325e0de3e18df29b41c060","datavalue":{"value":{"entity-type":"item","numeric-id":1827853,"id":"Q1827853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$1664363A-1CBB-42D6-9208-29038B7E4A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16545e9f886cc1aaeee9edfe775f0f02f55730a","datavalue":{"value":{"entity-type":"item","numeric-id":2266722,"id":"Q2266722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$FDAC48B3-A65E-4189-BBF2-4C40BC8CD9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b213c52a222d7efa3932cc69bfa23b3c133ebca0","datavalue":{"value":{"entity-type":"item","numeric-id":4521527,"id":"Q4521527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$38B5ACBC-99D9-498A-86E1-BCD90FBB7AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$70EB40E0-2A71-4CE2-B3C7-1848C6AA9826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ad7df6fc66261f0adbf0d71d21cd6218acbb91","datavalue":{"value":{"entity-type":"item","numeric-id":4047571,"id":"Q4047571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$DFBD2553-CEFD-4E47-89B6-8A757F025ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fefa2eaa9c8d7ff032801bb7e88915526c19adfc","datavalue":{"value":{"entity-type":"item","numeric-id":2482110,"id":"Q2482110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$D6F71DF2-2443-4384-9CA2-9E7BEB1D5BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a9c646d12d557ede4b6d9ea0171fbcc08e831fe","datavalue":{"value":{"entity-type":"item","numeric-id":2264685,"id":"Q2264685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2464161$AA5B3595-6EA3-45B1-A7F4-131DDF31B73B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b32a6611f0f5aadde7cc77e8fa95fa775d8ab62","datavalue":{"value":"10.1016/J.JCTB.2007.07.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2464161$AC924C0B-1229-45BF-B889-25E1B1ABC89D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74a5efd0ade566877d97b34c730ed966580db288","datavalue":{"value":{"entity-type":"item","numeric-id":5487777,"id":"Q5487777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f458f3c37fe92a861c9cbe7381e8fe792e2a5626","datavalue":{"value":{"amount":"+0.8202233910560608","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":"Q2464161$4EFC2648-AE10-4B7F-BC0A-B93D054345D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"973de912780a7f54af2756bc432d0f3257a3f1ed","datavalue":{"value":{"entity-type":"item","numeric-id":4508373,"id":"Q4508373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caaa2cab8abfd6dcee4804a395b74c1ea01df195","datavalue":{"value":{"amount":"+0.8026993274688721","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":"Q2464161$7780158A-AB33-4664-99B2-CEAEB3E09B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7afe8944286952462b440ed5e551ef94ffd9aedb","datavalue":{"value":{"entity-type":"item","numeric-id":879162,"id":"Q879162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a915dbaecfbcdd7a61f3fb25596c93d8588f4f9","datavalue":{"value":{"amount":"+0.7807068824768066","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":"Q2464161$62F701EA-B57D-4110-AAEA-8FD2D9B399A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"433b985a33ae25095bf9fa04e32d2262eb37e427","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5f0e8eee3b360ddd37dcd674fb799efc14fe4ad","datavalue":{"value":{"amount":"+0.7747220993041992","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":"Q2464161$28803E27-20EA-4FCA-B715-BF533FF145E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4014382a1a1c460f2e7526f6ed34829228eb8060","datavalue":{"value":{"entity-type":"item","numeric-id":1932477,"id":"Q1932477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d3c0b4afdb90b2bdfe306a13177eae7a8686a95","datavalue":{"value":{"amount":"+0.7713619470596313","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":"Q2464161$C5997F93-8582-4439-8EC7-5D2A6DBC8B3D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2464161","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2464161"}}}}}