{"entities":{"Q1773195":{"pageid":1783937,"ns":120,"title":"Item:Q1773195","lastrevid":68923119,"modified":"2026-04-13T03:08:13Z","type":"item","id":"Q1773195","labels":{"en":{"language":"en","value":"\\(k\\)-colour partitions of acyclic tournaments"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2161306"}},"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":"Q1773195$CBC52896-C346-4499-98D8-C0508391A558","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"59327c0ef0f7fc0ec87e90da81e40ac0eaa60de0","datavalue":{"value":{"text":"\\(k\\)-colour partitions of acyclic tournaments","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1773195$7F7C2C73-C2E4-4D07-B7A3-0C9B79DA3629","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ff4743c7927d409db158e93da7542d133bc2fe98","datavalue":{"value":"1063.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1773195$0F612DF1-FA44-4626-9CD4-3B85D24BB74E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2af70425acb43b522080c2361a7f98fa59d6967c","datavalue":{"value":{"entity-type":"item","numeric-id":922947,"id":"Q922947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1773195$5314051E-5408-4821-B2A6-E08ECEBB1034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1aba592a2f2e26376d265a66af59cbe52c26437","datavalue":{"value":{"entity-type":"item","numeric-id":1652379,"id":"Q1652379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1773195$0DF9804D-6CC3-4E21-9C37-D4B38B39D548","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1773195$36A5FF40-CD6A-4956-8465-142107CE7BB4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00916f50a25833282b599fa13c2d7aac3ea8143a","datavalue":{"value":{"time":"+2005-04-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":"Q1773195$1B127924-07A1-4156-84EA-9C806A834370","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"571d4ac8e9748cb2ffddd0519e867fad7d3a6b1a","datavalue":{"value":"https://eudml.org/doc/124648","type":"string"},"datatype":"url"},"type":"statement","id":"Q1773195$6323D341-2A8C-4EB8-BED3-142F2A6E35DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fad54d2924d8e7cab74bd928da83588cf87d80a4","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1r5.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1773195$CE7D4C91-2C7D-4F80-B057-A9C711B2FD07","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e03768c6b2c1b4a3516fedfd39d01977d976bfd8","datavalue":{"value":"The authors consider a weighted digraph \\(G_k\\) with vertex set \\(V=\\{0,1,\\dots, n+1\\}\\) and \\(k\\) coloured copies of the edge set \\(E_m=\\{(i,j)\\in V\\times V\\mid i<j\\}\\) (\\(1\\leq m \\leq k\\)). The different copies of each edge can have different weights (costs), which are nonnegative and can be infinite. A \\(k\\)-colour partition (\\(k\\)-CP) of \\(\\{1,2,\\dots, n\\}\\) is defined to be a set of \\(k\\) paths from 0 to \\(n+1\\), each path consisting of arcs from a single \\(E_m\\), one path for each \\(m\\), with each of the nodes 1 to \\(n\\) in exactly one of the paths. The focus of the paper is on minimum cost \\(k\\)-CPs. The authors show how to find a minimum cost \\(k\\)-CP, in time \\({\\mathcal O}(k^2n^{2k})\\), by applying a shortest-path algorithm to an associated graph. They show that the problem of deciding whether a spanning subgraph of \\(G_k\\) includes a \\(k\\)-CP is NP-complete. They give a polyhedral description of the problem, that is, a half-space description for the convex hull of the incidence vectors of \\(k\\)-CPs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1773195$A0356BA3-27D4-422F-90B9-DADFC3DCCC11","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"da4d0e7cb40bc0b3317e46d43560da36a2bb5480","datavalue":{"value":{"entity-type":"item","numeric-id":796109,"id":"Q796109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1773195$E93FD160-2E3F-45D9-A50D-9160959019A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1773195$6B316E71-015B-49D0-88EA-124BFD82E5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1773195$DAF7B642-591A-4019-B532-88923E89A3BB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"79c690e486a6eaa8e108c4af2226f9bc283711bc","datavalue":{"value":"2161306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1773195$A81DCF7B-38DD-4620-814A-158F113BC0D4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7043ae6c9be8694f3959ce43bd348b855ba501c4","datavalue":{"value":"path partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1773195$83643C01-2CBB-4731-800D-9B4BD6B4CA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"124e38f8641397e76cedce1d27fbc99119a40e5b","datavalue":{"value":"minimum cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1773195$37675029-644B-498F-AF37-5731BB7A855C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1773195$D580F954-D49A-41E8-9721-560884DBF12F","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":"Q1773195$9A5239FB-7BE3-4F39-A9F4-5E9B4D0B4FFF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0934056640f3f669b213cf2698c0b2ceb475c192","datavalue":{"value":"bafkreiepxwzvjgq4ylzbw5avzlocsotcwltbqwregr6wjkienehoajlmo4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1773195$75F0AD28-6873-411B-BF26-ABA2AE184A5A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e768883fa5b11ae62bb6dbfd3c028d90b750000","datavalue":{"value":{"entity-type":"item","numeric-id":4393303,"id":"Q4393303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e5896dc375b1c230fa9a9fb1bbb2ba26fa19241","datavalue":{"value":{"amount":"+0.8988296","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":"Q1773195$705ADF8B-74EE-4029-A3D4-B950C2A786D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a5f374172d6a86dc484e18e5afc4ba27da13e0","datavalue":{"value":{"entity-type":"item","numeric-id":4407964,"id":"Q4407964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e372d8a6f1b34b6df97c92d9fbd39b0b2ae139cf","datavalue":{"value":{"amount":"+0.89324677","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":"Q1773195$6F3F7362-3019-429A-8A55-B4C9B38E94FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"489a298f7407c7f6824f83fb1e8e4e6db883d41d","datavalue":{"value":{"entity-type":"item","numeric-id":276612,"id":"Q276612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c99e7b22a03762735fa1fd5733b2c0667576954","datavalue":{"value":{"amount":"+0.8902088","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":"Q1773195$65A9DA23-9270-45E0-A8EA-79E026494B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4602891e65594c4b665119971f35495d20180a84","datavalue":{"value":{"entity-type":"item","numeric-id":5324106,"id":"Q5324106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b725886e8fd32d3c9b5b48f59891da05d32e652","datavalue":{"value":{"amount":"+0.8860667","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":"Q1773195$22348DB3-4834-4470-9AD8-E2EBBFF1FA73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0ee2f9b66090c5d17272dbc2fdc01bf61b2210f","datavalue":{"value":{"entity-type":"item","numeric-id":6107479,"id":"Q6107479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d24c2f7d5416501631e2b31c6e77bc1efdf4ec0","datavalue":{"value":{"amount":"+0.88594246","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":"Q1773195$205B8401-0C16-4031-A110-B99DBEF4C8C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65abd20bb6f7d4576cbdae3f3425250d7bd9ca66","datavalue":{"value":{"entity-type":"item","numeric-id":1082350,"id":"Q1082350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06213cf3e0059c2e56534510e5eb1942ceb31f3a","datavalue":{"value":{"amount":"+0.88516605","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":"Q1773195$0B893176-6D9D-4A75-8EB7-9AE710DA1758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f4a867c1828050372bd0b3e9d8b937cee4a36a0","datavalue":{"value":{"entity-type":"item","numeric-id":2352522,"id":"Q2352522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3cea6975eacfa1a8d96246d83237743f7c6099b","datavalue":{"value":{"amount":"+0.8844162","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":"Q1773195$E44540CD-0B22-4A04-B0DC-B8301AED91CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e10efd32e267924b8a7d461fc8521b217ca0c91","datavalue":{"value":{"entity-type":"item","numeric-id":2998637,"id":"Q2998637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d2ce9fd8982e58426534899a0edbcd366f5ba22","datavalue":{"value":{"amount":"+0.87711096","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":"Q1773195$97A15F4B-1AF6-4179-BC95-9DAB5F03A101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6afbc509fcdad486ace343e41b18e6236f33a6ed","datavalue":{"value":{"entity-type":"item","numeric-id":547779,"id":"Q547779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73117381aea121ff6fa6dc1d5a65d341c2764276","datavalue":{"value":{"amount":"+0.872549","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":"Q1773195$75F52720-F6FC-4025-94AE-DF67C1BF8117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8075689f9e688e7f9cf39031bc96a6519a1c66c6","datavalue":{"value":{"entity-type":"item","numeric-id":5069071,"id":"Q5069071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"829c8ff265fb7783be6a7348431128e245484a52","datavalue":{"value":{"amount":"+0.87055945","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":"Q1773195$D713C584-A392-41A9-850D-23AE1C9F3AF0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(k\\)-colour partitions of acyclic tournaments","badges":[]}}}}}