{"entities":{"Q1184343":{"pageid":1195092,"ns":120,"title":"Item:Q1184343","lastrevid":70212687,"modified":"2026-04-13T13:12:01Z","type":"item","id":"Q1184343","labels":{"en":{"language":"en","value":"The traveling salesman problem in graphs with some excluded minors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 34343"}},"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":"Q1184343$74BDE4C6-30B7-48B0-8284-55FC81E5B141","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"07e93f416ac9a46c56af093f187484e8db841294","datavalue":{"value":{"text":"The traveling salesman problem in graphs with some excluded minors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1184343$89C9BBE4-8BBC-4256-B148-E2B292C09692","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11a2b158b3d46cad1a7e42dc0da35c005dfa7fb2","datavalue":{"value":"0780.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$7AF926BA-09D1-4850-AA69-D65B27755C14","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd5d8e316f56c67bd8a5e8bb3d43908c9354a31b","datavalue":{"value":"10.1007/BF01585700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$24C02229-E332-4E6F-B87B-3F573C14D757","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"39d7f725839a3071bb210d2dbb4156b1a4a192f4","datavalue":{"value":{"entity-type":"item","numeric-id":1184342,"id":"Q1184342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$21AAF179-D350-4B29-8804-1FE8AD66C693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95894cc2c440030f2044973e851310826ac5f3dc","datavalue":{"value":{"entity-type":"item","numeric-id":595679,"id":"Q595679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$3BAD31B6-3803-47EF-AEEC-D4D7121780D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$58CDA380-8B12-493B-983C-78EA38318780","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184343$BCFC605F-2629-4403-8274-916D082C5B97","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1611b77a89cc6a5f5ce9836ddb1fab5cacd5939a","datavalue":{"value":"Let \\(G=(V,E)\\) be a finite, loopless, undirected graph with vertex set \\(V\\) and edge set \\(E\\) having non-negative edge weights. A tour \\(T\\) of \\(G\\) is a closed walk that passes through each vertex of \\(G\\). The length of \\(T\\) is the sum of the lengths of the edges in \\(T\\). The Graphical Traveling Salesman Problem is that of finding a tour in \\(G\\) of minimum length. The authors characterize those graphs for which the convex hull of all solutions is given by the non-negativity constraints and the classical cut constraints. This characterization is given in terms of excluded minors. A constructive characterization is also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$984FE2A5-E007-4345-B709-DFD5541599F5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$E0588F77-F774-41CD-B6A4-930B440EDFF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$C53642E5-EB82-4958-BBE4-61BA33A27A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$85367D80-7D00-4BDB-B765-6E7ABB231408","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39280fc3904532cfe9e97706ae7161186d866006","datavalue":{"value":"34343","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$A9B57276-A498-4659-B06E-CFF3B3090BB8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"398999db83e6f0b9619e9606c6c09b8be1baa252","datavalue":{"value":"traveling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$7BD4F156-A34D-491D-8794-901CCBA74F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f723d2180f9757755404dae8103cb0f2c8383940","datavalue":{"value":"Eulerian graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$18E4D487-A1CA-483C-AD20-C3B0F86E4C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"579172068de96f7207eab70f6ed34d3150cd4308","datavalue":{"value":"Hamilton cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$806F317D-DC26-4899-BD4A-70B2173F49EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87b1445f21a754960c1f8704f1da6d7571086047","datavalue":{"value":"tour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$0E7A4AD6-DFBB-4AD5-BA53-2DB9B19AF7B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65bd34070aaf54b27536b874611d93a4ce51fc08","datavalue":{"value":"walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$0A7718F6-4DA3-4594-A947-BDE7728476CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"697626a6c5ea4a7921eba4e0f3fdba17e2e290d9","datavalue":{"value":"convex hull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$F0E41AD5-9AD7-4551-8680-81B014EBDC22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$AA969499-0A55-44EB-8EC6-412B328BA718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"218f3a114d42fa5daa9cf93a111516a570439f2d","datavalue":{"value":"excluded minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184343$F3ABD356-B1E5-4DAD-B10D-44CA0B0730EB","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":"Q1184343$F42FD5A9-AE27-4B60-92CE-654B393C15BA","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":"Q1184343$A73A771A-B300-49AF-9927-D7C3DA26E5D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$37DACB42-8C6C-40BF-B560-AAE8FA7724C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9e8a2a2ba09a34750ac91787a928d451826bfdc","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$999FCBCC-5B77-4632-8B4E-8B8301962989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c211e55116d68a1af38ddb2786888a3b5b61452","datavalue":{"value":{"entity-type":"item","numeric-id":3773723,"id":"Q3773723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$44AFC2A1-4A7F-4767-9F7C-0AF660EA1844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9cdc996ad6a2d6bc6c15f31d7c4c57ae7effab5","datavalue":{"value":{"entity-type":"item","numeric-id":3888840,"id":"Q3888840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$531204D5-E95F-44A0-8408-D377CD40A438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70a0003673cca99bcda918db1c0035f694b2d4d6","datavalue":{"value":{"entity-type":"item","numeric-id":5512793,"id":"Q5512793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$BE60987F-99EE-48DF-8C64-7566588ACC72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e36b52136c0479dac8c6e2301c0cd7cab48576a","datavalue":{"value":{"entity-type":"item","numeric-id":3220355,"id":"Q3220355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$27390D90-B4D8-46A3-B112-7A6119F2BF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6580b367a8c77254b89faa8bd3605a5190689d8b","datavalue":{"value":{"entity-type":"item","numeric-id":4285636,"id":"Q4285636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$E0E39DDC-6907-4EB9-AA4D-7540D9186342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$A9360C9B-F6E7-4894-9D17-5680712C39F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1ba0f71b10e95fd9c744c7f525e1858155d38c7","datavalue":{"value":{"entity-type":"item","numeric-id":3682240,"id":"Q3682240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$65CE3151-8E71-4617-9059-141F500B166E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce8d8f1a1624709769a8a693e9a1bc1f953b847e","datavalue":{"value":{"entity-type":"item","numeric-id":3674397,"id":"Q3674397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184343$DBD9A375-11E2-4396-8142-6E1437349B54","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"10c99d780d5300085a0f1e14e2f5951324e3baaf","datavalue":{"value":"https://doi.org/10.1007/bf01585700","type":"string"},"datatype":"url"},"type":"statement","id":"Q1184343$C6CF42E5-7069-4ECD-954D-A10DA9BF92BB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"443b1bf5ab7b49f37c147d6b2e572e3526fc40f7","datavalue":{"value":"W1981894795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184343$F35BE14E-C765-4792-8EBE-BD792213B919","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989c04bf82204d9c4f258df667b337206aaff748","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ddcbe74788cb49f5fba11a6253b61c1568cd8eb","datavalue":{"value":{"amount":"+0.8260511159896851","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":"Q1184343$B9198E15-D865-473D-BE22-0A332412DA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa2ca783ddd5c824367539c40d44d14489495152","datavalue":{"value":{"entity-type":"item","numeric-id":3773723,"id":"Q3773723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"718facba221cf0d5b494cd41db2826d8e62ab7f1","datavalue":{"value":{"amount":"+0.7774943709373474","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":"Q1184343$A0667823-E2BB-4882-863E-61B9975ED253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6483acb24068cfe0c6560e079660faa523de53a","datavalue":{"value":{"entity-type":"item","numeric-id":2476987,"id":"Q2476987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca5277f0f59d6589d544953d06767809d04b3b4c","datavalue":{"value":{"amount":"+0.7677795886993408","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":"Q1184343$C94496C8-B902-4D78-AC7B-427F95A9E0F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"179d747ed860bf01fdb064ebc3fd5ce0c780ce6e","datavalue":{"value":{"entity-type":"item","numeric-id":1752607,"id":"Q1752607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74a383e559da7f3dd4e6629a72b37cf6fbcc45c6","datavalue":{"value":{"amount":"+0.7622541189193726","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":"Q1184343$444EC558-7C93-474E-8D27-AFA447D1BB16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b404e7a6346cf12b8a12e0465d620e85ea80bdb","datavalue":{"value":{"entity-type":"item","numeric-id":4308563,"id":"Q4308563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e2babbaad93bc5216c45d317697bf9d00dc9f8b","datavalue":{"value":{"amount":"+0.7577025294303894","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":"Q1184343$A114188B-2507-41FE-8E11-D6BB1B217343","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The traveling salesman problem in graphs with some excluded minors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_traveling_salesman_problem_in_graphs_with_some_excluded_minors"}}}}}