{"entities":{"Q719273":{"pageid":721122,"ns":120,"title":"Item:Q719273","lastrevid":51343385,"modified":"2026-01-17T20:33:04Z","type":"item","id":"Q719273","labels":{"en":{"language":"en","value":"On the hardness of finding near-optimal multicuts in directed acyclic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5955890"}},"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":"Q719273$8A5375AC-6EA6-44FD-B977-F5BDC7482FC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cc42ca0b79e1c3da5cbf9007dd347bd569e6ea40","datavalue":{"value":{"text":"On the hardness of finding near-optimal multicuts in directed acyclic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q719273$4D950885-0BBD-4AD3-ACD5-9C734C892E40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a8e5835bf60c03e45213bd96ff52d92ea049394","datavalue":{"value":"1222.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$437AF857-9546-41AD-80AC-1B3922487FC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e68aae125f3f228ea3080ac3bc34c23ecc9ecd10","datavalue":{"value":{"entity-type":"item","numeric-id":346490,"id":"Q346490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$AEBB4AF8-8290-41B7-82AD-79349637FDF2","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":"Q719273$E37034D7-4395-4BFB-9012-03BDA3D9F461","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"150a41d2600a9b6bb2d57bcce319d1e2cca67717","datavalue":{"value":{"time":"+2011-10-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":"Q719273$1A67A825-29AE-4EFC-AEF8-468077E93730","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$07480782-AD55-4EFA-90A6-560D4A33E368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$710A8996-8DCE-454E-89E0-C49B1C0EDC1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$4A502529-CEFA-464D-86B5-D29B16C1F6D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$D7C61C2A-8F0B-4A15-ABE2-6B01B173680D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"733c7284154b6e80dbeee3002ba8adb2f095cacb","datavalue":{"value":"5955890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$5996D4EF-4400-42EE-8A3D-2FD75F041D52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4080b483fd9f575e4eff0edc14e0f1330693728","datavalue":{"value":"multicuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q719273$B6BAB516-2866-430A-8BCF-D2336F553B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2155b1f0f1b7934ea2f00e74be522bfbe52774","datavalue":{"value":"directed acyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q719273$1F829BA8-3AF1-48DC-AB7E-0FA941171FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c01a51105b1602eb458a8a0d5669470424318df0","datavalue":{"value":"\\(\\mathcal{APX}\\)-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q719273$B08941EB-67E0-441F-ADFB-3A39F9692E25","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":"Q719273$E697A2CC-2DF7-4935-B221-830EB3C3CA46","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea92f1c54ef84a49a6778529eb7a72107ab388b6","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.06.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q719273$C37BB339-C218-4672-AB0D-A7C1E0463403","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b22af3de6528e9edefb39ac0dee58c7b75a665dd","datavalue":{"value":"W2024751798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$847B7FE2-9966-482A-82DD-75FBF4BD3AD8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f44a76b5719daa58c59d178eeffb178e71bb9e","datavalue":{"value":{"entity-type":"item","numeric-id":1566710,"id":"Q1566710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$416E24BF-17B4-447C-A6A6-4FC6338384EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed7f15608500f95f5d7779a6e9f1bdd6365fa3a","datavalue":{"value":{"entity-type":"item","numeric-id":2643793,"id":"Q2643793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$832565E6-8AD4-43B0-B6E7-01C13895E4F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92931248062f2d15f3a521281a6c8060cd668e3e","datavalue":{"value":{"entity-type":"item","numeric-id":944745,"id":"Q944745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$6A680BA5-8E9D-4DCF-8848-2F611EA249B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832a7ad41572172e5555bf91ea79aa1e789ef798","datavalue":{"value":{"entity-type":"item","numeric-id":444380,"id":"Q444380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$EFA7C89B-A335-4707-9E3E-3DAFA31001DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"553889d62f085decb36da3b155922c1773b65e9f","datavalue":{"value":{"entity-type":"item","numeric-id":4458884,"id":"Q4458884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$B3973373-9DDF-408D-8DBA-E58C1F593DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffc0f37120c3fc43c2fea1a11a4e6eb759cdb9db","datavalue":{"value":{"entity-type":"item","numeric-id":2458939,"id":"Q2458939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$C2523D99-B9FF-4BCA-9B8E-C2CD3855D8B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"293934a962fb8e9e831b1b947b760d8dc941f21b","datavalue":{"value":{"entity-type":"item","numeric-id":2931415,"id":"Q2931415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$72157A33-2852-47D2-AB21-41A57D11CCC9","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":"Q719273$C1B13E3A-922C-4662-A389-E34FF69F0B13","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":"Q719273$65E714ED-A7E6-4F4F-BD1B-76AA82025C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$AD111E2A-17A4-45EB-9354-4049F2025B13","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":"Q719273$E46BEED9-2D0D-446C-84CC-661C3585A765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ef25dcaca47a5224dc8bf68ba789427e2dbeca8","datavalue":{"value":{"entity-type":"item","numeric-id":679443,"id":"Q679443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$CE9F6D0F-59ED-4BDD-B2CF-F61976D5E8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"827b2242d0488a47d148123d5f6a4b55ceef2bb5","datavalue":{"value":{"entity-type":"item","numeric-id":4819693,"id":"Q4819693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$CF18F2C8-2D5D-4C15-BC0D-D0C3B6D28C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f393042fbc5995c1fa174cc93e380846c4a30ff","datavalue":{"value":{"entity-type":"item","numeric-id":2379958,"id":"Q2379958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$0280D94B-6FB9-45BB-8DFC-CC0239133C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11b46d5a08a02e0a6fc718b6c2fa28f6247aa555","datavalue":{"value":{"entity-type":"item","numeric-id":818146,"id":"Q818146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$E170044B-6153-4381-B3AD-20F9BBC1D35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c571b640c1516f4ca2b62caa77bbdebe8bf825d0","datavalue":{"value":{"entity-type":"item","numeric-id":5736116,"id":"Q5736116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$8113A62A-83AA-48FB-AFD5-4F81FBDC3291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"167507a49c8cbea5342ed0259ac705047224f9a0","datavalue":{"value":{"entity-type":"item","numeric-id":930893,"id":"Q930893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$2D7B59F6-FCE7-43DA-B31C-52B8890F3794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1930d1972738cb597a9cfdee1b9e39b637b3dc3e","datavalue":{"value":{"entity-type":"item","numeric-id":4170247,"id":"Q4170247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$11CC32F0-A88B-47DE-BB10-B532165E6E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12600cb24649ba9815ffcfab5b752a2fd38d0d39","datavalue":{"value":{"entity-type":"item","numeric-id":1850539,"id":"Q1850539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$982D80F4-7057-4519-8E25-435A191BCB55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$29E3296B-09DC-469B-88E5-FA714DA79FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e511b859cdfbb396c346654ef2b832d4248dced","datavalue":{"value":{"entity-type":"item","numeric-id":1250228,"id":"Q1250228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$F45F1F81-7E59-428B-B647-F319FB1993E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"914899f8dadac090b69c03dc3d80a0a5ceec2c58","datavalue":{"value":{"entity-type":"item","numeric-id":3341921,"id":"Q3341921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q719273$51B52545-BA80-4F6F-BA36-4C239545E81B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"437518021ac87db2bedb921d469b3c11ac6e0d11","datavalue":{"value":"10.1016/J.TCS.2011.06.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q719273$F45A65E8-3667-49A9-A0B2-E225240D360F","rank":"normal"}],"P1643":[{"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":"dc2a8fe189dbc7ef4f63ef66a7de0211718adca7","datavalue":{"value":{"amount":"+0.8724331855773926","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":"Q719273$1FF44F33-D789-4F18-818B-53354D302D76","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":"41b3ee15d5e0c814c65d66838b8724cdb770c7ab","datavalue":{"value":{"amount":"+0.840697705745697","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":"Q719273$AC9920E6-DEC3-4280-87C5-C15B44BE9225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06905766501038a4bf8ad8ebcebf43cc6564ccf6","datavalue":{"value":{"entity-type":"item","numeric-id":2931415,"id":"Q2931415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3eac67e3e3fb3f498601f750c22df8fd8847064","datavalue":{"value":{"amount":"+0.8234562873840332","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":"Q719273$AF608BB6-FEEA-4755-88A8-5B0C56E84968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"202e0c7c71007a198001daf07e3214570e8dfb0e","datavalue":{"value":{"entity-type":"item","numeric-id":4458884,"id":"Q4458884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1885289bf83320ebd3937f0400e9e6bb2eeadf35","datavalue":{"value":{"amount":"+0.8174996376037598","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":"Q719273$4EFFC144-2034-4CC0-8673-DFC295E79913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75eaab6cd6ff3bc92adbca6523b9ba1549a1bfc0","datavalue":{"value":{"entity-type":"item","numeric-id":2741506,"id":"Q2741506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"432c8ffb41dcfe6a6fe326c6001e921a7b110dbf","datavalue":{"value":{"amount":"+0.8174052834510803","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":"Q719273$14102C83-22F3-4956-862C-AECE16D333FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:719273","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:719273"}}}}}