{"entities":{"Q1751487":{"pageid":1762229,"ns":120,"title":"Item:Q1751487","lastrevid":70830045,"modified":"2026-04-13T17:32:01Z","type":"item","id":"Q1751487","labels":{"en":{"language":"en","value":"On graphs of the cone decompositions for the min-cut and max-cut problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873326"}},"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":"Q1751487$D37A240C-3248-4423-869F-5119EE107664","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c3094059b9b2dcdad620bba229d2bae4f5ae9a59","datavalue":{"value":{"text":"On graphs of the cone decompositions for the min-cut and max-cut problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1751487$09FA0ABD-A85D-4CA0-8A21-AB1EFFF63FDB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09702d6ad5ecff99d32f7ab6286e1bf08da2f605","datavalue":{"value":"1457.90165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$43D1C659-AF5C-47AD-9E99-742F0334A1F6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96b656928d8a1c63b9778f0511058b8213fa3c07","datavalue":{"value":"10.1155/2016/7863650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$15B843D3-2D7F-457F-BBCA-3AF68D396B10","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9914a29ccd593c1bb223ad8f0338324462339ace","datavalue":{"value":{"entity-type":"item","numeric-id":1689898,"id":"Q1689898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$BCEF8BDB-EFC3-4623-9880-50ACAA20D526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e35af66a765aeef4985ea2f9cac9da117f266fd7","datavalue":{"value":{"entity-type":"item","numeric-id":219655,"id":"Q219655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$3171425E-6938-41F6-8516-EC3A4AEA38F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4d14f6de16fedb57ef2f0703ad32e93709741b1","datavalue":{"value":{"entity-type":"item","numeric-id":162459,"id":"Q162459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$248D8322-7BBC-47BD-B865-5AB4AB1D9385","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1751487$447C8C70-89DF-4974-AC7A-F27EA08CE3B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1475f1e0ed39515d76249738ab08fc081243d05","datavalue":{"value":"Summary: We consider maximum and minimum cut problems with nonnegative weights of edges. We define the graphs of the cone decompositions and find a linear clique number for the min-cut problem and a superpolynomial clique number for the max-cut problem. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1751487$42A688B4-0AED-4BFF-A080-D4404D27E496","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$92105C47-5997-497A-9DF6-E6BB4B543D13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7420518da9a398d9584019bb4944332dd9a0b14","datavalue":{"value":"6873326","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$5225058B-300E-46AA-B089-C8FE74E15442","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d12b1b15761398e9734c224f0009c3dded254bf","datavalue":{"value":"clique number, time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1751487$7AD0CA30-919D-4026-91B1-043C8A169D75","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"23fea7d84f9077954388c86645e42a12ef2a2f88","datavalue":{"value":"Q59124627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$64AC2CB6-F6FA-45F8-B944-A1A8D11D02D8","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":"Q1751487$D0DC6608-4877-407A-949A-845D3C975A3B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fe4da9113c3ace31c5c6d0441e30a471884ae2af","datavalue":{"value":"https://doi.org/10.1155/2016/7863650","type":"string"},"datatype":"url"},"type":"statement","id":"Q1751487$8EF5A2A8-CFF0-4569-8311-69326CAEE85A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1e20d9f3c240b9bacf5569578ad6a56ac64737f4","datavalue":{"value":"W2270504252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$3A24C93C-4408-4BA7-A849-27BAD3780B89","rank":"normal"}],"P223":[{"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":"Q1751487$638F9162-01DF-4A6E-990C-F9E7E2001DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$72D7A67E-1765-4164-9514-F01AAA771334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8233216d3b0e1adeae55391a8c1581d8fb0d8499","datavalue":{"value":{"entity-type":"item","numeric-id":4314500,"id":"Q4314500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$1E66E788-C8D8-48E5-B8BB-38BCB31B0820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84987f8d99e2687c6f6c7c2c8dbcea6e278915f","datavalue":{"value":{"entity-type":"item","numeric-id":4377588,"id":"Q4377588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$151EC2B5-6ABF-4778-A16E-8B6A26B534AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a31bead779bd596b3920cfd06b2841c8eae14ef","datavalue":{"value":{"entity-type":"item","numeric-id":393848,"id":"Q393848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$7C449A90-6761-462E-B8AF-FEF257E29464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28ec90f78e20c6b51cead969fb0bc118f9cacbe","datavalue":{"value":{"entity-type":"item","numeric-id":1326866,"id":"Q1326866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$185E058B-4B1B-4672-97E2-C605A3D45D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35c67431c82daaa23477c244089abdb4aa44e8f0","datavalue":{"value":{"entity-type":"item","numeric-id":5691934,"id":"Q5691934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$4C9A37F3-93BA-4F50-AFF8-A5090443B4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0388dcd39169e10a675fa53d30f8911665054641","datavalue":{"value":{"entity-type":"item","numeric-id":5902168,"id":"Q5902168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$5C607432-2BC0-4FB0-8AED-6A53004DB3E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"839074748b5f47b62af2cf41163406f4acafc8ca","datavalue":{"value":{"entity-type":"item","numeric-id":5465691,"id":"Q5465691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$47E845ED-BEA4-4CD8-B8CA-8640F7393757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871b0b619dcdcfea503ebb95e9e10caab2448bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4726054,"id":"Q4726054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$9CD266E2-E8BE-4914-9CB4-477ECECC1327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7a72878d69140e2975d99e42da8c6e1d4334056","datavalue":{"value":{"entity-type":"item","numeric-id":1426123,"id":"Q1426123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$0A061866-744E-42CB-8F6D-B0DCCCC999E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"952282ac2b54d0d2f4d44d71f523648720fff81a","datavalue":{"value":{"entity-type":"item","numeric-id":2638384,"id":"Q2638384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$4BB09DBC-3673-4AEE-A090-9A89BEB7494F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e96b239a1f8a99f7481b596758663a90ffbe5be9","datavalue":{"value":{"entity-type":"item","numeric-id":2560819,"id":"Q2560819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$4913260B-7315-4020-8780-491F0F6BA5EB","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"cc2bea559441c31cdd4de1de0072aa10ac5e1e22","datavalue":{"value":"journals/ijmmsc/BondarenkoN16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1751487$C3FE4BB1-D6C0-4632-9120-0EDAD765EA6B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dda384a463437e7688d2c1e28d2160406fc37673","datavalue":{"value":{"entity-type":"item","numeric-id":4500843,"id":"Q4500843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4cf20c0d19b92fcd986e60b26b8ec3a871b0cbd","datavalue":{"value":{"amount":"+0.8177447319030762","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":"Q1751487$FEDF9CC4-8315-41A0-8A1D-82BE5E8E6C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6b3046e2c652be128d1f1c69eab689a4357ec13","datavalue":{"value":{"entity-type":"item","numeric-id":4840774,"id":"Q4840774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"259c1907eb9123d1f0492ee115b26de2c09ae7a3","datavalue":{"value":{"amount":"+0.807100236415863","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":"Q1751487$4124658A-D1CE-4091-A243-66C1AFD2BBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510d90a2bb3d1d2c8b7934817dc315f359d8bbd2","datavalue":{"value":{"entity-type":"item","numeric-id":1199475,"id":"Q1199475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c33fad0fcda531b607b802536e289b672c835439","datavalue":{"value":{"amount":"+0.8061219453811646","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":"Q1751487$E3C7BA68-B92D-4DB1-B4AA-8467CB33F17E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c545f7eaaebe488117bb38a008ac8abfc496d30d","datavalue":{"value":{"entity-type":"item","numeric-id":3059313,"id":"Q3059313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4d3b1b655a8ca501c0a6ac4fa4fe1a39fb98c26","datavalue":{"value":{"amount":"+0.7902308106422424","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":"Q1751487$F16B373B-8146-40B7-A12F-A96582C0F4A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2fc4800f7e611f30b3ee512a5bd26b76210fcac","datavalue":{"value":{"entity-type":"item","numeric-id":1179735,"id":"Q1179735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79b5108871dbc5fee5ef5d502c1941c76fd08920","datavalue":{"value":{"amount":"+0.7843483090400696","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":"Q1751487$48E9487D-0B04-49D2-89A5-B9FB4B430C71","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1751487$380DB369-54E2-4D12-9BDF-218D02C5D6B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On graphs of the cone decompositions for the min-cut and max-cut problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_graphs_of_the_cone_decompositions_for_the_min-cut_and_max-cut_problems"}}}}}