{"entities":{"Q2492190":{"pageid":2502933,"ns":120,"title":"Item:Q2492190","lastrevid":49848772,"modified":"2026-01-11T07:05:55Z","type":"item","id":"Q2492190","labels":{"en":{"language":"en","value":"Minimum cost and list homomorphisms to semicomplete digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5030480"}},"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":"Q2492190$81B033DF-78FB-4CA9-884B-5E98355BC5BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"efa6032f16cfd16a05b11f65b9c48970a814ea5a","datavalue":{"value":{"text":"Minimum cost and list homomorphisms to semicomplete digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2492190$B9FC17AF-B249-41E5-A4EC-7E7044B7A019","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e99e98b53c81baf8b9ff60f6d3c68268e76b250","datavalue":{"value":"1138.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$29AB5B2C-6D2D-447B-A5A6-5007EF2D0964","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":"Q2492190$0AC3D1D8-25D0-4BF3-A249-512D60C65621","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":"Q2492190$DA310113-40E3-44A7-96C0-45CD78B72D0F","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":"Q2492190$FA658C24-41EB-45EB-B1C7-999A69F4D775","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":"Q2492190$B5F97C85-7F21-46FD-B7CC-3D3F4F8B22C8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"21437c544db1978eeec04a4cbdd682f98ee3c97e","datavalue":{"value":{"time":"+2006-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2492190$A727B5E0-73F6-4347-93A0-9BB4C1E88C85","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1605efe3729ac0704a7dce1a62b1873b1b111654","datavalue":{"value":"The homomorphism problem for a digraph \\(H\\) is to determine whether a directed or undirected input graph \\(D\\) admits a homomorphism to \\(H\\). The list homomorphism problem for \\(H\\) is a generalization of the homomorphism problem for \\(H\\), where every vertex is assigned a set of possible colors.   The paper obtains dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when \\(H\\) is a semicomplete digraph, in which there is at least one arc between any two vertices. The dichotomy for the list homomorphism problem coincides with the one obtained by early researchers for the homomorphism problem when \\(H\\) is a semicomplete digraph in that both problems are polynomial solvable if \\(H\\) has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different in that the problem is polynomial time solvable if \\(H\\) is acyclic or \\(H\\) is a cycle of length 2 or 3; otherwise, the problem is NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492190$8AF26AE7-8146-4731-9361-77075380093C","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":"Q2492190$642A0F35-2649-461D-846C-BCA5F85FCBC4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$1271095B-5387-4198-9054-B477D96266E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$E821FEBB-0C44-498F-B1B8-B0720D4BCD1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4036d64b600ce503afff8f76d7d02065452dcea0","datavalue":{"value":"5030480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$EC61DCCB-3E77-4A2B-B807-F0E7E9FC368F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492190$B6745F49-1523-44DF-9107-72E065D8A235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492190$195E46B7-2453-4374-A53C-06C3EC0607BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d92cd9a7fa9095787346c6bca4de3ca7ee817d4e","datavalue":{"value":"semicomplete digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2492190$63385DDB-45C1-4C68-A7C2-88EE3A9E7681","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":"Q2492190$5C06CAE6-7448-4F0B-AB9B-741A835CF230","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c8a47b1260ebe8308a0c3ac43d13d4f7511ecb62","datavalue":{"value":"https://doi.org/10.1016/j.dam.2005.11.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2492190$ADEB9201-5AE3-4B42-A35F-236487BC086D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"31b3bb6ae4fcdf24a6856a4b54f574e7c412c0f0","datavalue":{"value":"W2126491855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$94860E33-8D26-43CF-823E-67FB8ED4FF41","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad7c1d4e8b0d5f48c9538674580566bab83d2c8","datavalue":{"value":{"entity-type":"item","numeric-id":705491,"id":"Q705491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$BA0CF619-B2B6-49C5-BB4B-0D60B0AE2F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078b931a9fe3dac15986eadf2f67608aa760ec66","datavalue":{"value":{"entity-type":"item","numeric-id":3809822,"id":"Q3809822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$7F079E6B-A0BF-432A-99DF-459752E9B752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ca92c5e9c033964322f96db99eac2d4a15c7ec0","datavalue":{"value":{"entity-type":"item","numeric-id":3834066,"id":"Q3834066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$94253F68-53AC-4DA7-AF25-F7DAF77B88AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24ab94925d77f68bbba9bb500216729d0045622e","datavalue":{"value":{"entity-type":"item","numeric-id":1363736,"id":"Q1363736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$A5C6EE8D-BCED-48B1-BA80-5CFE3CA84E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17329aeb7c77f3079291a06d18c322c312b1a335","datavalue":{"value":{"entity-type":"item","numeric-id":2946643,"id":"Q2946643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$8788E200-FCA4-4132-ACF1-0F0B714CC5AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89d50425a411ca72b811e943d5cc6f778ad1844a","datavalue":{"value":{"entity-type":"item","numeric-id":5897200,"id":"Q5897200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$FD6FDD14-D695-4456-AFBE-8A2BEAB4006F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"258bb7aacd601e088fcab733be55793de05f9f91","datavalue":{"value":{"entity-type":"item","numeric-id":5715675,"id":"Q5715675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$551F56A6-AD7E-4087-BC7B-86BD31BBDE2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8642e43399918dd25428e88f97c67cc7af24ce9","datavalue":{"value":{"entity-type":"item","numeric-id":3576659,"id":"Q3576659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$181E4B24-8442-46EF-9559-ADF5ABD58D0F","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":"Q2492190$9DA82633-6561-4B25-837F-FE5993CE66BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5c6061c3f6daf7454d0e9c58daef6f441530aa","datavalue":{"value":{"entity-type":"item","numeric-id":4210136,"id":"Q4210136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$DDF97D8E-D395-4B31-9825-3160A5B44D92","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":"Q2492190$A06E39AD-2557-4464-A5EF-01C6E6BCE765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"904fbef47fb47aeed5d61932cfa523281bd82c37","datavalue":{"value":{"entity-type":"item","numeric-id":286971,"id":"Q286971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$AAACEE74-3864-4543-89AC-76AEF43321CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5c00eac674f112d4343779c2e1fed9255824ad4","datavalue":{"value":{"entity-type":"item","numeric-id":5710145,"id":"Q5710145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$09C89E66-6438-4802-9F83-3A7D79A5DC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b71ebcf94b7d9f1900f711045d833ef13e14fe33","datavalue":{"value":{"entity-type":"item","numeric-id":1183345,"id":"Q1183345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$EF374763-D139-46C3-BDCA-784E323944AB","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":"Q2492190$8A731258-2217-4867-BE1D-A3DD78836AD2","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":"Q2492190$E8A0FB8B-0B0B-474B-B27D-E779FA109E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a633e84f28e974524d6f21199618016457237af","datavalue":{"value":{"entity-type":"item","numeric-id":4828516,"id":"Q4828516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$13F60AAF-D82E-4726-8DBE-63845A1C9EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4228cd5d2851d42123b7df5d8107602c3e5b439a","datavalue":{"value":{"entity-type":"item","numeric-id":4225377,"id":"Q4225377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$D22C4FF3-7C0F-4356-97D3-F0F25F49A420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6033cbdfc75fbf185f01d24946516a20af7924a6","datavalue":{"value":{"entity-type":"item","numeric-id":4483540,"id":"Q4483540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2492190$2404E1EC-6DB3-48F6-8C62-49817750A70B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a02f06df5760465186b07a353d7079d0f5d5b5d6","datavalue":{"value":"10.1016/J.DAM.2005.11.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2492190$BA3D6481-9B79-465D-9BAE-60D77703349F","rank":"normal"}],"P1643":[{"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":"6d380f839a7367d7a650c91a8396988cd0a2d3c5","datavalue":{"value":{"amount":"+0.8998396396636963","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":"Q2492190$BBAF9235-85AD-4AB8-8EC0-3C511570D200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d93d3d60cf6a7bb466af020312c9f496db0b2dd6","datavalue":{"value":{"entity-type":"item","numeric-id":968147,"id":"Q968147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f54e3e44979893f9cfc61cf69f783fd5e89c2b7","datavalue":{"value":{"amount":"+0.8997721076011658","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":"Q2492190$A68F612B-91CC-47BE-9B5A-E9FFAB8B0FBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0ad3c7cd3499284e8f6faa487d8959959e4ba3b","datavalue":{"value":{"entity-type":"item","numeric-id":5505675,"id":"Q5505675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a17a410fc9e1c221d83f52afa753b0c6ef5183aa","datavalue":{"value":{"amount":"+0.8925554156303406","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":"Q2492190$D6505DAF-B1A5-42A8-B33E-B678F76FBB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3b699040b70e37bcb39beec55059189d1bf297f","datavalue":{"value":{"entity-type":"item","numeric-id":3565872,"id":"Q3565872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c16ae62abce7bd7fd610609029ddcf427a7733e","datavalue":{"value":{"amount":"+0.8876504898071289","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":"Q2492190$B39F3C3A-BA84-4894-9D35-8F28F2FFACD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d95a71ebb045a6a5ae78dea0f84f3c9ade21390","datavalue":{"value":{"entity-type":"item","numeric-id":844220,"id":"Q844220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8b107fb571424a57cc50ab7605ba7b5ce48c04","datavalue":{"value":{"amount":"+0.8761102557182312","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":"Q2492190$0A4493D9-BBD0-4883-8A42-086EDFAEE5DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2492190","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2492190"}}}}}