{"entities":{"Q844220":{"pageid":846068,"ns":120,"title":"Item:Q844220","lastrevid":64766631,"modified":"2026-04-11T22:05:03Z","type":"item","id":"Q844220","labels":{"en":{"language":"en","value":"Minimum cost homomorphism dichotomy for oriented cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5659946"}},"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":"Q844220$5FE4E1B4-9768-497C-988E-36003665854A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af5d6a868201f83fba6c542e0d7f20086fc339c0","datavalue":{"value":{"text":"Minimum cost homomorphism dichotomy for oriented cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q844220$F0BBF987-E14F-4349-B5EF-CABFFE67B82E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"93fa120747ad8695a3ceb9563f884f55a81563d5","datavalue":{"value":"1188.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844220$A510869C-5243-4059-90D1-6F09C9BBCDCA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d62d1b98a8e47330bd8d09b4c364147d7b3d1f6","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$1B8948B5-956F-40D0-B4E3-2C43A97E4258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71308cb4f9689a990fced8d311f30cbbc4f5cd69","datavalue":{"value":{"entity-type":"item","numeric-id":385509,"id":"Q385509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$72D4DE6E-1664-41E8-89EF-CB8938942268","rank":"normal"},{"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":"Q844220$6AF1C6AE-2C6A-4330-94C2-930A238DA3A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$34157352-FB37-4B8D-BCA8-C1E767431FB0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"160ae7be62905e153a649a9a4d09ab3aa02ded62","datavalue":{"value":{"time":"+2010-01-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q844220$0099B4AE-536B-47A9-9E7A-7925DBD61556","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5aa85b8f649b3c91d05f02cdb8c299abcd7eb88a","datavalue":{"value":"It can be shown that if a reflexive digraph \\(H\\) has no Min-Max ordering, then \\(\\text{MinMax}(H)\\) is NP-hard, and that if a semi-complete multipartite digraph \\(H\\) has neither Min-Max ordering nor \\(k\\)-Min-Max ordering, then \\(\\text{MinMax}(H)\\) is NP-hard. The present paper shows that the same result as for the semi-compete multipartite digraphs holds for oriented cycles. In fact, it proves a graph-theoretic dichotomy for the complexity of \\(\\text{MinMax}(H)\\) when \\(H\\) is an oriented cycle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q844220$34C02275-4769-477A-B503-C5D96ADB40FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844220$56A513A9-5881-4F73-8312-24E8EB0FB5DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8311706cfa78501af430110a58ed9b39af131122","datavalue":{"value":"5659946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844220$818DC436-B783-4FF0-8F29-B2FE91408337","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q844220$1C11DDF2-B4FA-4E6F-AF95-AFA339A4D124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q844220$32685EB6-A4F2-474E-AE5C-5C4BD1C503D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"124e38f8641397e76cedce1d27fbc99119a40e5b","datavalue":{"value":"minimum cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q844220$4E767E99-35CE-4DEA-8EB0-7CF206287D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b987be565609a99f8666695ba29384cff98521a9","datavalue":{"value":"dichotomy","type":"string"},"datatype":"string"},"type":"statement","id":"Q844220$6D4352D3-4B21-404D-B9C6-651019F708E0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$F7A09BA9-E8F0-4234-BD99-A5F1338F11BC","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":"Q844220$0BDC684E-D708-4A76-84F9-26310862209E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5676417650155204a5271d81bc19492cc13ebfe5","datavalue":{"value":"https://doi.org/10.1007/s00373-009-0853-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q844220$ABCB1EFE-65B6-4ABA-A39F-C70A5356CA25","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42fbb61e63728180392aac5d9a5c1706c5da9d9b","datavalue":{"value":"W2154562890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844220$EA113253-649A-4DB9-818A-A465834B3199","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"211a561ecb8f3c2d9b642276ac6f1596fb4ebc88","datavalue":{"value":{"entity-type":"item","numeric-id":4500916,"id":"Q4500916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$84425375-1801-4D1A-9E76-B4118615A230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"893e17efaa1f10a4b9f97a3bd671e2acd56551dc","datavalue":{"value":{"entity-type":"item","numeric-id":2753538,"id":"Q2753538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$CE531D73-D403-4750-A033-A06CA84E04A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36144b018ef727ae18de988d6f2f30fd59bdbdac","datavalue":{"value":{"entity-type":"item","numeric-id":5458527,"id":"Q5458527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$3F82167F-BBB8-4672-9415-61C9A9B30D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eae035393804c377802a6675e42d0a5b6390da4f","datavalue":{"value":{"entity-type":"item","numeric-id":2427539,"id":"Q2427539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$425A8DB8-42FB-4E6A-8935-B6D219674DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57b08779c6de561929f7c492333936fe11ded572","datavalue":{"value":{"entity-type":"item","numeric-id":2492190,"id":"Q2492190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$3285EADD-93BF-4B78-9D3A-63E55AF4E254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2294979344525fd42a4fa3932c95a87b35d6b7e","datavalue":{"value":{"entity-type":"item","numeric-id":947134,"id":"Q947134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$DD02B7AD-D0FE-45F1-ADD0-3ADE33ACC442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6af6c4f4d53058648e0da16c36b931cfa17d3f00","datavalue":{"value":{"entity-type":"item","numeric-id":3648516,"id":"Q3648516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$C2D5B1BD-642A-4262-A224-E89C31766D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a83dd767e7472796602730814ff55ddcf8201ff","datavalue":{"value":{"entity-type":"item","numeric-id":2492189,"id":"Q2492189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$62115964-90F0-413B-A4EB-1AEAF6F9EFE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5028065ceb61d7fbbcc8d74c873e6a965e0cc43f","datavalue":{"value":{"entity-type":"item","numeric-id":1110530,"id":"Q1110530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$335C7235-32B9-4DCE-A506-D9F8489A2B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58abb47d283f11d319166bc8a771025f9e31cf9b","datavalue":{"value":{"entity-type":"item","numeric-id":4780787,"id":"Q4780787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$0C910775-5802-4B57-AC67-7FE90F44297B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72636d83503e896e571d6f2c09be11cb7bc2ca51","datavalue":{"value":{"entity-type":"item","numeric-id":1977431,"id":"Q1977431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$C97C122C-1AD8-4081-8689-40AC46D9CD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fd9783d7f3da253431895c7c9c58155bfbb1f4c","datavalue":{"value":{"entity-type":"item","numeric-id":4432211,"id":"Q4432211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$24FB0757-B9D6-403B-B99B-D185F9625258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$CD69D151-D780-4A83-8463-8D0F12133D18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b85e726a9dea4d901959cd5845fa226b41795ec","datavalue":{"value":{"entity-type":"item","numeric-id":4837649,"id":"Q4837649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$783147AE-4C86-48AB-9008-10B53AEB810D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccab1fa5b33ce5963e4fca3149490ae54d1388c0","datavalue":{"value":{"entity-type":"item","numeric-id":4943070,"id":"Q4943070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$C7F28484-784F-4D29-885C-530BBCD55DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d85eb8073cb4ff1478a098ef140f418cb1c410e","datavalue":{"value":{"entity-type":"item","numeric-id":4719325,"id":"Q4719325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q844220$781BF05C-96E8-4AC5-8D54-92E2EC990224","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3c6f318280aaf0ff6ee0d8bd71ae017832d006e","datavalue":{"value":"10.1007/S00373-009-0853-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q844220$ED3AD96B-6571-4384-A588-825DD8383180","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb3490e17cc0d376c2e73df1c190987343c929aa","datavalue":{"value":{"entity-type":"item","numeric-id":5458527,"id":"Q5458527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a475ac11a89ef9f01777b197b84bf6a5d54d008b","datavalue":{"value":{"amount":"+0.8573112487792969","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":"Q844220$A92A9AD9-E61E-4E77-82FF-BF9B269ED731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d4aa7729b1cb46cceb49b5f66f825c1d921155","datavalue":{"value":{"entity-type":"item","numeric-id":3511431,"id":"Q3511431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e255e8a6a7ac0a54cb1197261f0db393df78eef8","datavalue":{"value":{"amount":"+0.8419222235679626","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":"Q844220$07FA7A6F-7B6C-4037-8B46-5687872C9A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"944469da24f69e72868369006847fee316a1ba61","datavalue":{"value":{"entity-type":"item","numeric-id":4915189,"id":"Q4915189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c5a3b6b747cae7c7ae18b4a666f84cf905ff8e3","datavalue":{"value":{"amount":"+0.8244439959526062","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":"Q844220$D8DCA44E-4219-4052-9C91-A5C8DD962DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65ae0959436711b2a7a54fd98033e1442c5ffe7d","datavalue":{"value":{"entity-type":"item","numeric-id":2492190,"id":"Q2492190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45caccd58a60b9c6ad7e73723989771201defd34","datavalue":{"value":{"amount":"+0.7984863519668579","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":"Q844220$36EA791D-2D6B-44CD-A37A-FD8EDE4D054C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5c4f3fb49cd59a4ec62e33e07dd9bebdd39493d","datavalue":{"value":{"entity-type":"item","numeric-id":3648516,"id":"Q3648516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4317db7de9938dcab3ca9a795e6044bfde761887","datavalue":{"value":{"amount":"+0.7889400124549866","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":"Q844220$27E6E24A-F5DE-460F-A689-46F45036596A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum cost homomorphism dichotomy for oriented cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_cost_homomorphism_dichotomy_for_oriented_cycles"}}}}}