{"entities":{"Q391767":{"pageid":393534,"ns":120,"title":"Item:Q391767","lastrevid":61531233,"modified":"2026-04-10T23:58:05Z","type":"item","id":"Q391767","labels":{"en":{"language":"en","value":"The complexity of multicut and mixed multicut problems in (di)graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6244484"}},"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":"Q391767$DEB5409D-04EA-4E0F-9A24-A13D2AB6EBCA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ad9b35b2448ac6815c4914446415757975efbe9","datavalue":{"value":{"text":"The complexity of multicut and mixed multicut problems in (di)graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q391767$0ECC2F9A-95A8-43B7-854E-5D2C5CF7DD5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cad9160e56be7a14ac6fda1a43f398068a9fafd8","datavalue":{"value":"1352.05173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$2D06DE19-EF67-4F7F-AC29-149AE6460FC6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$95D87392-E8E5-45E9-886C-6E7C0082CDEE","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":"Q391767$31652A7B-4BA6-42EE-9600-BA6414D20670","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":"Q391767$D57B893C-E9EC-4381-817E-C1018AAFC05D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a7f0ce9f8644dc92186acf7aa59a26f9b811cbd","datavalue":{"value":{"time":"+2014-01-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q391767$77B5BF81-DB89-4262-B1D0-3A0420D0A572","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$E1EEEF01-70BF-4551-AD50-4D475DD5031F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$8A84CAA0-F7E9-4BB1-8C21-D93F97ECD8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$0F50395C-97A6-43C2-9F8C-91B564EE2F52","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"efa2635a1fa273ab9492dc3b082afc7dc43ce108","datavalue":{"value":"6244484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$01891C41-23A8-4446-A8EE-A6FB17B0BAED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3888e4321007424eccfc4c0021cff8a7cf7efbc","datavalue":{"value":"multicut","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$7D3D7FBA-1750-4879-8639-EA28600EAC3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0de429593140647dc3a596da860845a1c045f74","datavalue":{"value":"mixed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$014A0F1D-3107-4129-8204-A0C092012BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f03fc57050fe0418f736e874f8f28ee2494f9bd4","datavalue":{"value":"mixed problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$FCFD6D59-4647-41B1-9DDB-84C06BE0997E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b987be565609a99f8666695ba29384cff98521a9","datavalue":{"value":"dichotomy","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$1DAFD998-9D1A-4B2B-B80C-24EF2D96FFA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$A9B7822A-BFE3-4E56-8E42-2BB187A3D109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d55d12d8e521239dbfda14f4fd78e26c893c51bc","datavalue":{"value":"feedback arc set","type":"string"},"datatype":"string"},"type":"statement","id":"Q391767$1785243C-3805-48D0-BB42-704CB6B407FE","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":"Q391767$19D08466-1B95-47A0-93D9-045F74069732","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9044a31beb7a1f3bcfd15480bbe741fe993db6c","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2013.10.022","type":"string"},"datatype":"url"},"type":"statement","id":"Q391767$6EFABEF1-D338-44BE-9270-5C3FE110B661","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08338092bd9269e9fb429c18bffef63d998b041b","datavalue":{"value":"W2027659362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$0EB825AC-5332-4F8D-B42C-429944733885","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$A9E0E218-F569-4704-9945-906067F9C5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$99C40DBA-7018-4691-99B0-9823164D3494","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa4bad6022be1ab4807d1603bbe9f696daca96c8","datavalue":{"value":{"entity-type":"item","numeric-id":5419116,"id":"Q5419116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$73D46ED7-60F0-4E06-A145-C94F5F85BB80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd62c8f70b6c9b33356cd90ffc8196962a5babc3","datavalue":{"value":{"entity-type":"item","numeric-id":707131,"id":"Q707131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$607FD540-FBBC-4C5F-87CD-230BA6561F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c36b42b281969cc247486ad758e619940ccb2d97","datavalue":{"value":{"entity-type":"item","numeric-id":4305362,"id":"Q4305362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$DDB0245C-F040-4638-A382-2A2ACF5CD831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4e037221fe3588e4c8af02add0bdce47017c377","datavalue":{"value":{"entity-type":"item","numeric-id":4632450,"id":"Q4632450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q391767$5B3A2348-8A91-4EE1-9A48-A339324DA27B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"17ba8a534fb76c483f2411423c5d28c44b21b0ff","datavalue":{"value":"10.1016/J.TCS.2013.10.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q391767$A708D1E4-75B8-44BA-BCBA-6C243E13B888","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecf5c8c18900af751c2b8b399de41520579114b0","datavalue":{"value":{"entity-type":"item","numeric-id":5897992,"id":"Q5897992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09da50ff0d9ea292337fe5ece9e47895dfc474bb","datavalue":{"value":{"amount":"+0.8112291097640991","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":"Q391767$6F60051C-D219-4E79-B823-E5C41A2DEB8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6c7c30a19e94748c3c24cee401e932a01bd6d58","datavalue":{"value":{"entity-type":"item","numeric-id":944745,"id":"Q944745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91faf7526664f3ada4de63cfe3b0498679d4aae3","datavalue":{"value":{"amount":"+0.8057007193565369","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":"Q391767$6CB0EF79-5AF3-4629-8D63-E6C649860398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f21111e5fd5dc36430036196b5a5839eeadbe7e","datavalue":{"value":{"entity-type":"item","numeric-id":5494921,"id":"Q5494921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1f682f4edee4e5c1e0a60bfa8ea9b28f260218e","datavalue":{"value":{"amount":"+0.7904295325279236","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":"Q391767$AB7D20C6-970D-40B5-B299-539B5C16A564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49a4e4aa75f1c4517acec64d12d1e584689af773","datavalue":{"value":{"entity-type":"item","numeric-id":2851464,"id":"Q2851464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a3b5b2300d3379db76c1d1884efbb483e3c0f13","datavalue":{"value":{"amount":"+0.784318208694458","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":"Q391767$B9D939EC-5C1D-409C-86EC-464CE103E410","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of multicut and mixed multicut problems in (di)graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_multicut_and_mixed_multicut_problems_in_(di)graphs"}}}}}