{"entities":{"Q1195644":{"pageid":1206393,"ns":120,"title":"Item:Q1195644","lastrevid":47100205,"modified":"2025-12-31T16:24:14Z","type":"item","id":"Q1195644","labels":{"en":{"language":"en","value":"Optimal arcs for the traveling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 85842"}},"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":"Q1195644$92699A73-E19F-4662-80AA-36C988C8B467","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79d1fe735918e6dac6d130b395ee760fba6cfb36","datavalue":{"value":{"text":"Optimal arcs for the traveling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1195644$8AB1945E-6906-4BFB-B874-D19230410E6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e2965c7cc63a48d6af15c1209b1833cf74822642","datavalue":{"value":"0760.90091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195644$179202E9-72CF-4541-A70D-8219D676A0FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6907c6aa39a8737a59e82728fc25d3885ba6b4f2","datavalue":{"value":"10.1016/0893-9659(92)90028-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195644$ADC23544-9BC1-48B5-8037-742E565A1E72","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b0a764e715c2b710a243fd5e819812b7e5e5e0d","datavalue":{"value":{"entity-type":"item","numeric-id":352990,"id":"Q352990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$8A2708E8-C5A6-4358-8777-3E9B212FD2F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"60e92c9f06012150d8158f8bfafc8319965c5fdc","datavalue":{"value":{"entity-type":"item","numeric-id":176247,"id":"Q176247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$067D5AE1-0BA5-43A7-8822-16FEDDDFA1D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4f871edb204a3f93a27c86f6b4e1f5cf46f281fc","datavalue":{"value":{"time":"+1993-01-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1195644$859F03E1-10A6-49B1-9768-43B655319A61","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"38e8c8576d3ff9cf3f476d56d22c9122fc4f6d19","datavalue":{"value":"This paper contains theoretical results and robust conclusions about the matrix structure of the traveling salesman problem. The results expand previous research advances of the author [ibid. 2, No. 3, 277-279 (1989; Zbl 0704.90075); and Linear Algebra Appl. 139, 53-62 (1990; Zbl 0727.90063) for classifying distance matrices; ibid. 160, 247-253 (1992; Zbl 0743.90078) for the 0,1 traveling salesman problem].   The classes of distance matrices which are analyzed are those for which an arc on an optimal tour can be identified in polynomial time. The 0,1 case is given special attention because it is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195644$79D3C5E8-91EB-4424-BF1E-9784CAF489B1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195644$020FE56C-58D4-42CD-BA4C-D033702C430C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f04cb107c866276264d48ab8bfb260960d0380b0","datavalue":{"value":"85842","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195644$887094B3-5F95-4AB9-9030-A89068203544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195644$99A12863-9694-47A7-B659-1BBE4FC4B680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1195644$C428F386-B5E4-4A06-B58D-D14E9B831AD9","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":"Q1195644$B90289D6-1258-429D-B6A8-78482A674AAF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80a637139ae1231cdd4105f9b9d2f2442110023b","datavalue":{"value":"https://doi.org/10.1016/0893-9659(92)90028-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1195644$6ECE6532-70FA-45C6-B08A-353122FAD69C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"85a4b5fe140efdea4402b3cef8a8d6e0d5956bc0","datavalue":{"value":"W2049644155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1195644$17294F99-AB2E-4B01-9EC9-3B7E004FBC4D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"81513165bc14b34749da52049c662f3b5f248c28","datavalue":{"value":{"entity-type":"item","numeric-id":917447,"id":"Q917447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$DDBA8EDB-3787-4E37-B50E-791CD641CBC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7565dcf9c6b001033130b1029fe7ad18f4c9ca07","datavalue":{"value":{"entity-type":"item","numeric-id":804474,"id":"Q804474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$AF62E11F-9C3E-4602-8748-8B359DB6A522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bfac2bf5d02ce54d406439d14b761d94560e21b","datavalue":{"value":{"entity-type":"item","numeric-id":1183142,"id":"Q1183142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$BB492051-F38A-438B-B6DF-A02B4721C4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f36929515ef0b92528e1af5f9f676c9138b6c57","datavalue":{"value":{"entity-type":"item","numeric-id":3778565,"id":"Q3778565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$57A2AB4D-AFCD-4C0D-9DC0-3534832474E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d150b48fc40427a6fd07dd4ef348e95109646212","datavalue":{"value":{"entity-type":"item","numeric-id":2639760,"id":"Q2639760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$31940CFA-0FEB-4B0A-951A-5485E8E21484","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c893b7b17db5da0cf71bed489830282949b84","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$2F180996-9557-41A6-86D1-FCE3C66DE9C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab46786b245f9a4c8c113847c9ff7bdda562dd55","datavalue":{"value":{"entity-type":"item","numeric-id":3989345,"id":"Q3989345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$18281EBA-8BC3-47EF-A1C2-16A6F02FB903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65399ef3a851a2b39762d4f87d35f7ce2de6153b","datavalue":{"value":{"entity-type":"item","numeric-id":1109689,"id":"Q1109689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$6B14169B-0EEC-431A-B2AC-052E017BC991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca5090218963f7454eb65bbbfc3a5878c945557f","datavalue":{"value":{"entity-type":"item","numeric-id":4162995,"id":"Q4162995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$1B578802-4B0F-420B-8B59-3364904AC440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eed3750329372eb2e9f0fa76ab40dbe2e6e1f15c","datavalue":{"value":{"entity-type":"item","numeric-id":1181042,"id":"Q1181042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1195644$9C2495AE-5E5D-4DF4-BAA6-539047D3192B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a293228ab49c3b428299dd40de067c447b3ebfe","datavalue":{"value":{"entity-type":"item","numeric-id":3989345,"id":"Q3989345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12cc9a96e79e34206c852d923311461d3fc76567","datavalue":{"value":{"amount":"+0.805422306060791","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":"Q1195644$AD9AF7CB-D161-4F7A-87A4-B346F08DD5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96f6731b252bf9da49501458669faace7cec8a41","datavalue":{"value":{"entity-type":"item","numeric-id":4845366,"id":"Q4845366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a66f44968a668ea2647ac12abce4224cb779ccc","datavalue":{"value":{"amount":"+0.7990560531616211","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":"Q1195644$FA9414E2-B26E-4C06-8FAB-9FFC87EE0F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0adff11c7c3ad9b96c86aab65f702621fd7a164f","datavalue":{"value":{"entity-type":"item","numeric-id":1116903,"id":"Q1116903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a66f44968a668ea2647ac12abce4224cb779ccc","datavalue":{"value":{"amount":"+0.7990560531616211","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":"Q1195644$60129878-9BD9-4C20-8E2D-E83CC9F91147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afea2376f96a54f51f7e63aff117211d6f19e1f3","datavalue":{"value":{"entity-type":"item","numeric-id":918426,"id":"Q918426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa83447490f02c5db399f5d98643c2cc48c076df","datavalue":{"value":{"amount":"+0.7932440042495728","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":"Q1195644$7192BB92-F4C7-4120-810D-2885E13858DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8c6d7d64d0f3c543d25ee0000324842232c4999","datavalue":{"value":{"entity-type":"item","numeric-id":3768703,"id":"Q3768703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c00ff226fda94b24c63be26253d1911b0eea1435","datavalue":{"value":{"amount":"+0.7843304872512817","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":"Q1195644$972A7AB5-7D26-4CCD-BE6E-AD2D2E4A95C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1195644","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1195644"}}}}}