{"entities":{"Q1174433":{"pageid":1185182,"ns":120,"title":"Item:Q1174433","lastrevid":66758424,"modified":"2026-04-12T12:40:18Z","type":"item","id":"Q1174433","labels":{"en":{"language":"en","value":"A note on line digraphs and the directed max-cut problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8714"}},"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":"Q1174433$52274A0B-45BB-46A0-A360-D630E4D60BAE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd06a274e70845b6332a97fcd757b18ef6ad2499","datavalue":{"value":{"text":"A note on line digraphs and the directed max-cut problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174433$8E15B357-F264-44F0-A20B-BEFA24BF3E8D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3b06a3a9a72d7a9363a63cbc55f6efd3893dfd93","datavalue":{"value":"0739.90070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$032D1A48-3A8F-44FA-B7CA-F83C4A8E9A3F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6daa8fafd3e6bc269629c92820659eda4fde8599","datavalue":{"value":"10.1016/0166-218X(90)90141-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$2B8EC535-482D-43A1-8A5B-B1C4A3639EB4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$B67510C4-5B2C-4E56-A505-A3D3F0861CC5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$886AC9B4-3F52-4A95-B56B-5592585306E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-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":"Q1174433$3DCFF524-F29D-4236-AA81-03CF06B27BD8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4bbc85e8520af08f574647a24fdd36c5b3914a47","datavalue":{"value":"The support of a simple digraph is the undirected graph arising when directions of edges are ignored. The authors prove that recognizing supports of line digraphs is an NP-complete problem. Further, they observe that solvable cases of the directed max-cut problem arise from solvable cases of the maximum-weight stable set problem via supports of line digraphs. In particular, they investigate digraphs \\(G\\) such that the support of the line digraph \\(G\\) is perfect.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$3E0AAD02-4D36-4318-8532-BC67568C9F32","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$1AA0F4F9-F60F-48F3-B072-8AB0F2C84CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$4931A1BD-1326-4E13-9A76-53049FEBF6BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$9C642A02-9FE5-47BB-9F32-69B851C11D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$0D9CD4E9-C81A-4AFC-A83B-90A082FC0070","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c41855ce27e1adc3fbc97516b545a5d7c648fb4d","datavalue":{"value":"8714","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$AC047E10-371E-4C95-A427-2D157CA253CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$DCEAAB83-6170-4793-9F7F-57CB48C15A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f27fd70206ab65e5b2cef58dc14631d5414a6232","datavalue":{"value":"supports of line digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$BB167B20-692F-4975-998C-3FC5FD8E1A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$BD452D20-E25D-45EA-BCB0-1A5150E741E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b28ee42e62bdd24a062c87f2115069549e528d1","datavalue":{"value":"directed max-cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$A63A0721-5214-4E4E-B6F4-B128C23D36CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f58f8d2c26e4143c87a5e7562a4e3b407460cf90","datavalue":{"value":"maximum-weight stable set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174433$BCC6AEAA-DE2F-494A-911D-E03AC3B82FAF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5a8b5716bc29dee4849a02abb2efc7b4cabc4b7","datavalue":{"value":{"entity-type":"item","numeric-id":328466,"id":"Q328466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$0542CFA6-AC04-49E5-8FCF-C8C17DF1A872","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":"Q1174433$244F9411-7DBB-4820-BCE1-19FF8630E02C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"418cd5ed6d6440cc0b5986bca4aa93f90ad28c0f","datavalue":{"value":{"entity-type":"item","numeric-id":5570136,"id":"Q5570136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$4E598C3E-39E3-43EF-AC37-75DC89F37B93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84a1046121f2cb924d453d66d35f37deceef766","datavalue":{"value":{"entity-type":"item","numeric-id":3904382,"id":"Q3904382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$3A539184-257E-4723-A6D8-6B3D97CCC7D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe9461c49af81136ca85a9030a47fab2e9b98548","datavalue":{"value":{"entity-type":"item","numeric-id":3972131,"id":"Q3972131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$BEB79F57-66BE-40E9-A6CB-0604C3279824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33700daf3c6512d00dc11464b35bf8e524b4c45","datavalue":{"value":{"entity-type":"item","numeric-id":794657,"id":"Q794657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$B2CA6CF7-E7CC-47EA-B9C0-87185FE80F67","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":"Q1174433$AAE3A860-F849-447F-BE50-F3D325695DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$AB0044EB-40F0-447E-BA43-3C03366AEEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34bc8de7dff9e6ae38acf775674b87311a55dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1169411,"id":"Q1169411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$8B61A18A-9E59-4BC6-A815-9B06E4DD7329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49245e0aa29f3d0b8a4f3aa138d592837bd9a7fb","datavalue":{"value":{"entity-type":"item","numeric-id":4083461,"id":"Q4083461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174433$33F59BE2-BDC7-4049-B892-7D43463CE827","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d8daa3fb4090b805ab20d556001e3c6cf66b4f3f","datavalue":{"value":"Q126654022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174433$DC245784-7DD2-4AE7-BB0B-2EEDBA12BA97","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b05a2e04e131beaa224b9978deed7db27b23900","datavalue":{"value":{"entity-type":"item","numeric-id":3633002,"id":"Q3633002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3b6b75005406a6f07d954487874af7825e7c84d","datavalue":{"value":{"amount":"+0.90589696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$1EA9BACF-69B9-473F-A958-C32A1704BA56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"597af67d5a4a41fb56816a29bd4355d8549974c4","datavalue":{"value":{"entity-type":"item","numeric-id":3445498,"id":"Q3445498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55034a23b39c1899ae4da0319819a73af9241dca","datavalue":{"value":{"amount":"+0.9042127","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$C423E8C5-B948-4E04-B348-AABDF9ECD2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55cb3b7f0481e522d0d7b59ea5e3abffc3c57bf1","datavalue":{"value":{"entity-type":"item","numeric-id":4228209,"id":"Q4228209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95e07c99f4bef0c7318b08f3848f808a210714d7","datavalue":{"value":{"amount":"+0.8935874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$70361A65-0EC1-4C23-9B32-6F514EC6649B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af604c02533847f2796f0399b68d5c8cb7320cdf","datavalue":{"value":{"entity-type":"item","numeric-id":1926032,"id":"Q1926032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc77cbdb019089a10f3bfece93b72db130a9ca7e","datavalue":{"value":{"amount":"+0.889036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$3046E9F3-B68D-47EF-8C12-9FC52D207C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b48cdf2111db81e06274cc0ed94a0064298241c1","datavalue":{"value":{"entity-type":"item","numeric-id":2872084,"id":"Q2872084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec53341000993cc2d711accb2c27a9deec57941e","datavalue":{"value":{"amount":"+0.8825439","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$53F2F061-4B3E-48AF-8989-DA9A4F83A71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ee5857c299bb0623fb04239c1a2c1843c76eb0d","datavalue":{"value":{"entity-type":"item","numeric-id":5418765,"id":"Q5418765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"183f03e6af58aba1584978c5b6f2a5e72aef3016","datavalue":{"value":{"amount":"+0.8809943","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$9A4356E5-AD97-4F9E-99EE-305E44E4DA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc86003edbca598f36fdea826391d2e6473a75e7","datavalue":{"value":{"entity-type":"item","numeric-id":329544,"id":"Q329544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d180771ddcf5dfa406e00973e40d5508e1f5b9df","datavalue":{"value":{"amount":"+0.8808631","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$6377AA82-D838-4557-86FC-5CB6232670FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31a22379274a9ea60eebd87003d3d055db5e811e","datavalue":{"value":{"entity-type":"item","numeric-id":1029330,"id":"Q1029330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9453dee412c597bb78756cf4c6046850c0d6116","datavalue":{"value":{"amount":"+0.87877005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$0831BC95-B53A-45AD-BA25-1D0F266E9660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc9820b77d7faf0dc4b70c7d80d9ea8fd38eee6c","datavalue":{"value":{"entity-type":"item","numeric-id":2768265,"id":"Q2768265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c8d0604db279b1957237ecef20a0b68e7800ca2","datavalue":{"value":{"amount":"+0.8774601","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$9780263C-004F-43A0-8F50-C5D7B9D048F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab8c546431dc77859b2ee71c913c4a30b22dea2a","datavalue":{"value":{"entity-type":"item","numeric-id":1570888,"id":"Q1570888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"597608e075584e4231a247de12f1e734f4886922","datavalue":{"value":{"amount":"+0.87426704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1174433$2A0477B4-FD74-43D8-8FC5-FE6C1BAE50A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on line digraphs and the directed max-cut problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_line_digraphs_and_the_directed_max-cut_problem"}}}}}