{"entities":{"Q1740696":{"pageid":1751438,"ns":120,"title":"Item:Q1740696","lastrevid":73831260,"modified":"2026-04-14T17:25:17Z","type":"item","id":"Q1740696","labels":{"en":{"language":"en","value":"A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7050147"}},"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":"Q1740696$BF228A70-100F-4C7E-B0B7-2C2B891F5550","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5125a314a4a1df16841d7adcf7460130d03fc551","datavalue":{"value":{"text":"A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1740696$1D741C1C-9F1F-4095-8B8F-01F432AE6E27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5268b0380447307d474b69062ba684409c4f061","datavalue":{"value":"1422.68125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$97502580-34C1-4139-A195-E066986C0E15","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d58268156f8ce664e47b92662ca397a022d5f810","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$0AC66142-AAB9-497F-AE21-2CD281750D91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6fa552e3cd0ff1adea0b17fba705a13774eb3b7","datavalue":{"value":{"entity-type":"item","numeric-id":814930,"id":"Q814930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$329AC298-99E9-4790-A9B9-1D8412603E22","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$72593BA3-81F0-46A5-89E2-DE20CD102405","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fe967a6646fb6ad4126028ed66c1cfc1a0b6f1a6","datavalue":{"value":{"time":"+2019-05-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1740696$66985D64-9A88-4575-B4CB-A4D9ABE8BC94","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ede79685c8ca72184140974e0ff071fc3d9cc1c","datavalue":{"value":"https://arxiv.org/abs/1804.11102","type":"string"},"datatype":"url"},"type":"statement","id":"Q1740696$AACC2B21-B915-417A-A6DF-EBE1FBB372E0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$71E7E1ED-E8B0-4A10-B728-0C67AB10B824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$EFBDB754-B98F-435E-A734-3751E87985D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$9C38CFC6-FBAF-4D11-9491-A597AEC3EAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$F227BC50-31DF-4BFC-8E6E-A739D165C8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$D2D9669F-2BA4-4581-A0D4-AF9786BC0175","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"73694b99f859019f47955ccc4803b5a60d3692fb","datavalue":{"value":"7050147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$3FFA1FF1-0E16-4926-9905-49DAD9402B92","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5abbe2608084a7972c2175afb25edf2be63f2b","datavalue":{"value":"matching cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$C359B7C3-FDC0-4537-8571-9F3AE74691B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$2FA0C61E-0A36-480B-8F5A-7920803F44E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$E9B4FC2F-819C-438D-A744-CC914F17E104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$336C3C49-187F-4CE9-9F8D-2607AC75BA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"491073adb84794ac69dad93e698882d1730ec597","datavalue":{"value":"dichotomy theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$F4E2343E-C5BC-4E22-933A-ABB68433C1EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a4e152411e1a440272710f7a5a6ed494f898a11","datavalue":{"value":"decomposable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1740696$EE8A3158-86AE-4771-B30B-D65250E96DCC","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":"Q1740696$97FCE429-234B-4026-A9DE-86052746597A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"880eb62ae252dfa93f7ca78df92b61a1016423cd","datavalue":{"value":"W2798321768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$00E12E39-6BF3-4189-B0FC-C4C52634E418","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc2a691098384b0b7b2563137ef3da5da95ada96","datavalue":{"value":{"entity-type":"item","numeric-id":5916095,"id":"Q5916095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$F694661D-DAA7-4390-B95C-538AC1AEC30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$2E65EA80-7E1D-44C8-8D61-6AD497F4F712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$D7D2CDCA-3338-4962-96F8-4C9534C1D241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$45247CFC-C0FC-4233-9D70-5E0C01728C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4435696d97f8da0bf57d75929de82e9376b12bc3","datavalue":{"value":{"entity-type":"item","numeric-id":3652545,"id":"Q3652545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$2D3D2382-187E-4781-BB91-BAD1849EDAEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf2131213b8b985978b8cdf81067ad56a982647","datavalue":{"value":{"entity-type":"item","numeric-id":955037,"id":"Q955037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$53E51754-8040-4271-A297-6A3FA1C71B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2128fcc7dd131688ca80e86b9ccd3255436687ec","datavalue":{"value":{"entity-type":"item","numeric-id":3320412,"id":"Q3320412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$1545F12E-CBAA-4129-8EC1-CF9AB48C657F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0e6b90c16ae5fa1eac19212a306cb84ffec72b","datavalue":{"value":{"entity-type":"item","numeric-id":5613969,"id":"Q5613969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$96CB943A-02CB-4113-BF9F-943F87143A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6327224c4debc2501c4439bfd0d53425e1e3cd69","datavalue":{"value":{"entity-type":"item","numeric-id":4505015,"id":"Q4505015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$E8B48FE9-2010-4C08-B6B0-A3FD27D94DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e2bb90c8cf8d80fb6cdd156087f7560a367d5","datavalue":{"value":{"entity-type":"item","numeric-id":1578412,"id":"Q1578412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$7D6D7710-6E84-445D-841E-ACCE8835D46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$A2307062-034E-44DD-AB72-FE8267CC2464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b8d5def610d8b30d7ab358c662db6c5a666343e","datavalue":{"value":{"entity-type":"item","numeric-id":3956856,"id":"Q3956856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$E6F0E1A9-A3D1-4E2E-8EF7-550B3DA64927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec0438fd1c8404e37e26968776398d70fcae598d","datavalue":{"value":{"entity-type":"item","numeric-id":5636924,"id":"Q5636924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$50DD6CBF-4F77-4E2C-9E2C-EBEDF0F05B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7439459ecfe23165afda27d4bf107f319aba0aa","datavalue":{"value":{"entity-type":"item","numeric-id":897900,"id":"Q897900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$9667E478-F13D-4911-8ACB-7659EF9DFA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7416cd8122c06c493854ec1032afa9917851f8b0","datavalue":{"value":{"entity-type":"item","numeric-id":4636534,"id":"Q4636534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$C6713288-6621-4415-943B-CED2991F31B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c24df0acd582836f7cdc1f8ec419292eb9dd6a","datavalue":{"value":{"entity-type":"item","numeric-id":1400002,"id":"Q1400002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$EF7C3EC3-BDD8-4A9A-A335-D45305D01C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bf9a90e6ab9ca0076a53ea18244ec0e5b95bf74","datavalue":{"value":{"entity-type":"item","numeric-id":5203060,"id":"Q5203060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$1D92466D-8082-4E00-B100-D15EF59DBC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9940c7db31ae4803d6e40c0ef99f14a099d76364","datavalue":{"value":{"entity-type":"item","numeric-id":4448767,"id":"Q4448767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1740696$B9F78894-80E2-4231-8370-251C380C7B1C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2f2dad3c546c008758e8c3fb4c59ac72701332fc","datavalue":{"value":"Q129037185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$605FB811-A1CB-473B-858B-EC3D601E9368","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2830fb26c11eb9e1a8c5dd343a59ce476e0cd64","datavalue":{"value":"10.1016/J.TCS.2018.10.029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1740696$514D4B1A-C434-4EC6-8558-B68A7F44FF22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0902fb24b953445676093e68655b528b51119e7d","datavalue":{"value":{"entity-type":"item","numeric-id":4636534,"id":"Q4636534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bf2bf729cb29d3ba6fd9e2962c8a41b38b59050","datavalue":{"value":{"amount":"+0.9901135563850404","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":"Q1740696$6C54F756-3292-4747-A9FA-443E63CEA5E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c81cd9dcec640300d0c946736a0f3958c0146850","datavalue":{"value":{"entity-type":"item","numeric-id":955037,"id":"Q955037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"900e20186f1c391c0d55cfca98f7cc6f79158dea","datavalue":{"value":{"amount":"+0.8662846088409424","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":"Q1740696$79B84AC8-6371-475E-97E9-3532E7DCBD62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49d7c293d54ec099785fd9a0115c8cf1be1ec54b","datavalue":{"value":{"entity-type":"item","numeric-id":4448767,"id":"Q4448767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1b1fc2be283c2821649bcf45f985b591b4f17c6","datavalue":{"value":{"amount":"+0.8327831029891968","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":"Q1740696$3825DBF1-3267-4E01-9EF4-EDD542D8F051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edb48d53052b87de3d38ac90d38f58b660429b78","datavalue":{"value":{"entity-type":"item","numeric-id":3652545,"id":"Q3652545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a924a02d2ea21f9a686810bd2a97ccb9ed20cc9d","datavalue":{"value":{"amount":"+0.8267749547958374","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":"Q1740696$B8E073F1-0CFA-49AD-91B4-FCA10094D665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7513507b2110d503f0b06725e8a7d14f6a2997e3","datavalue":{"value":{"entity-type":"item","numeric-id":5902513,"id":"Q5902513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"288683effa5f7688b8d94b8b52985014a776cfbd","datavalue":{"value":{"amount":"+0.8256862163543701","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":"Q1740696$4EAD9B31-FEA3-41DD-A665-EC5948FD7B12","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complexity_dichotomy_for_matching_cut_in_(bipartite)_graphs_of_fixed_diameter"}}}}}