{"entities":{"Q1923593":{"pageid":1934335,"ns":120,"title":"Item:Q1923593","lastrevid":46394493,"modified":"2025-12-24T17:02:22Z","type":"item","id":"Q1923593","labels":{"en":{"language":"en","value":"Complexity of tree homomorphisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 933107"}},"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":"Q1923593$90833B79-0385-4343-B2D4-9A3FE621F4C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef7370e64e3bfd74cb8229cda5a0ad82870d5cd2","datavalue":{"value":{"text":"Complexity of tree homomorphisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1923593$92678EAB-7978-4D03-8495-27FFC3149A7E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74eaecc1885ba01824f38e8862553b2b4a6d3386","datavalue":{"value":"0868.05018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$4DBB5579-4AAB-4D3B-A230-F727F05FC202","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"756f47d13fc7bbf8d8b53cc141c26847b3d08a30","datavalue":{"value":"10.1016/0166-218X(96)00099-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$D0FB69D3-B574-4EF3-8624-435BE53DEDC7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$71BF56F6-5197-46EA-88DB-EBCC88C68FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$71A865AF-0A42-4F9B-8867-E304E1823C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6b19b09c7519f38384d021f845694abb1cfab04","datavalue":{"value":{"entity-type":"item","numeric-id":168189,"id":"Q168189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$CD7D388F-3513-47C4-8549-5EEB25E4E6D0","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":"Q1923593$0F1F7A4D-D1C6-48C1-9D94-41D4B2E98F15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f7f34121104d5a769836c4f5a4b60f968d0a4004","datavalue":{"value":{"time":"+1997-08-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":"Q1923593$DFBA431E-F577-48A0-9271-4764D6B8BCDE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1923593$D3E5D1FF-98A2-4112-BFD4-9BEDD79F3F8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9940dd57fee18276c02ab711920fbfd5b0c1267","datavalue":{"value":"Let \\(T\\) be an oriented tree and consider the complexity of deciding whether or not a given digraph is homomorphic to \\(T\\). A class of simple trees with NP-complete homomorphism problems is identified, the smallest tree having 45 vertices. A list of all subtrees that are necessary in order to get NP-complete homomorphism problems for a tree is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923593$FC044745-4D8B-48FF-9105-E34C25311895","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$1B7F3E41-3BBD-4C27-8FB6-11D44A9B1CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$C57ABB09-CD8F-4D6E-A900-0DC7526938A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$EE26EF18-F0A0-4B1C-81AA-F8680369920E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$CA1D300C-9465-4CC5-896A-6F778C115E64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c8d0f3b3052058651c0344995e401e8da514d8f8","datavalue":{"value":"933107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$82C1F2F8-9BE6-4A95-8B75-0B18F0A77121","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923593$F37DD12D-663F-4043-9EB2-A0C97665FB9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3feba1bfde94c1a4bb6966dd3e2b5cafd7b5cc20","datavalue":{"value":"homomorphism problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923593$4898027B-B3EE-4986-8CD7-D35670C89B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923593$E63A683F-B588-409D-99AE-C8D06BA8F481","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cbf074879019e41055b4d461d7d073f58abbd088","datavalue":{"value":{"entity-type":"item","numeric-id":210450,"id":"Q210450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$A32E0BC6-7F5D-4F6B-A8C1-FCD76C5C6C86","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":"Q1923593$25F07E6D-3828-4F69-9F34-F44996F64B4E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ade5a5172a0b2dc9f519d61c7175134ee8bc199","datavalue":{"value":{"entity-type":"item","numeric-id":911612,"id":"Q911612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$1D58227B-CA25-4C8B-802D-C2EB1A952250","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":"Q1923593$3AD437B8-C49C-425D-AA16-217635566F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98b621b31f596378d337a5257f1b9f1e39adfddc","datavalue":{"value":{"entity-type":"item","numeric-id":686279,"id":"Q686279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$33543840-FA89-406C-9F9C-B961FC0E4BF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e18975fbe96343fc0c778502af0d8435c15ebc5","datavalue":{"value":{"entity-type":"item","numeric-id":1842146,"id":"Q1842146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$D57BF405-C31D-4CC6-AAFA-D3CFB1446F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$E70C9632-E8B6-4880-8A89-D6631615AF8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7aaa9bb137fa2b1d06177861fbdb923853dbb86","datavalue":{"value":{"entity-type":"item","numeric-id":5248532,"id":"Q5248532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$545B7EB4-FEB1-45C2-9348-9C225BA75C8D","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":"Q1923593$256964A8-56FB-4631-A19B-9C3ECA5F3819","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":"Q1923593$27158A70-579C-4071-8CA8-F31EF50F04C1","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":"Q1923593$ADAF251A-5F66-4927-AE59-F37FFD0A9072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3eecaee66bd0ba87d34b0ec31abc7cbd696abfd","datavalue":{"value":{"entity-type":"item","numeric-id":1245971,"id":"Q1245971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$0820DAFD-9A31-465C-914D-B6DD1D8CEAA9","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":"Q1923593$5F3EEC5A-37B3-4A1C-9D5D-54FDD1734EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"676176244725ad505d74fb063bc848b0d22d5ecc","datavalue":{"value":{"entity-type":"item","numeric-id":751667,"id":"Q751667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$F6490DE5-56B0-41CB-BE78-0362445B4591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e67d001e0155770b04f208c6990101ba01f2cea","datavalue":{"value":{"entity-type":"item","numeric-id":686290,"id":"Q686290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$A5BC38D5-B7E6-4E31-AA0B-4463A564F13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d99101b30853333ff5ca3c17c825ec34ae9021e","datavalue":{"value":{"entity-type":"item","numeric-id":4889961,"id":"Q4889961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$2E9FE45B-DA1E-469D-9AAD-5276E58CB85A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade08e5950cef3f4816d2a20486aaffb965cd270","datavalue":{"value":{"entity-type":"item","numeric-id":4878664,"id":"Q4878664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$87AE8D39-30A4-4F89-ADAD-A745397EAF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"201de901ea95934bb102d54c382e7d0e410a0681","datavalue":{"value":{"entity-type":"item","numeric-id":1316647,"id":"Q1316647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$B45529D7-D734-48F4-89E4-F0060CF64DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b7fdc0b7d95e617afde9148fde7c2c48031293","datavalue":{"value":{"entity-type":"item","numeric-id":1336655,"id":"Q1336655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$5664B616-439F-492D-8047-252F339767B1","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":"Q1923593$675B584E-AD7D-4841-9906-8543EA1EA5C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8002546a42d967ab22805fe7698fd4d1aa8f6401","datavalue":{"value":{"entity-type":"item","numeric-id":3968465,"id":"Q3968465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$712BBEEA-6A41-44E8-819D-B67E573AE666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccbb2b9035e545c37b778a0955a9777fcf8a5fd1","datavalue":{"value":{"entity-type":"item","numeric-id":798680,"id":"Q798680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$E3CFD6B5-2F27-4B41-BD55-4F5883823FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16fa441ee502da32a1be25c5ce44d3fc6fb06b6f","datavalue":{"value":{"entity-type":"item","numeric-id":4857535,"id":"Q4857535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923593$D293015B-8D41-4ECF-8480-E5D5E3F29E09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e63c29877d0d9f9fcaee5b27a65e39902a756667","datavalue":{"value":"W2086916741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923593$2943D1E7-43EA-4F5F-8A5B-326AFEE4F0AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfbd3a17c8f119fffc038086479c2dc451253d82","datavalue":{"value":{"entity-type":"item","numeric-id":4878664,"id":"Q4878664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b7e77268974127c45a5713c0251a5959d47a592","datavalue":{"value":{"amount":"+0.8360180258750916","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":"Q1923593$0658D55E-C090-404C-A1C4-60FA32616125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09a39ef3aa42a29f33aff24525108e1be392ffe5","datavalue":{"value":{"entity-type":"item","numeric-id":4889961,"id":"Q4889961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abb19565821624a0f0427fdfbca9e24813194ff6","datavalue":{"value":{"amount":"+0.8356441259384155","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":"Q1923593$A065233C-CF28-4E54-AA76-F0B7C2A3C2F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e6f24c7e7ec3246e87a45030d0c9d65796c0ad3","datavalue":{"value":{"entity-type":"item","numeric-id":1356452,"id":"Q1356452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f649e9e8a25b76b12396d3c4c95c901f13648cf1","datavalue":{"value":{"amount":"+0.8034666776657104","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":"Q1923593$AD19118A-8D56-4FE2-9D00-231DAC1E36E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aa77270b477f25b4e23cd74552ef638b0f3809f","datavalue":{"value":{"entity-type":"item","numeric-id":1686250,"id":"Q1686250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d00e9c7171d8896bb3d90856f345bb4977a4af31","datavalue":{"value":{"amount":"+0.7855942249298096","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":"Q1923593$183ED1E3-F899-4D6F-B479-3D07FFA9D291","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1923593","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1923593"}}}}}