{"entities":{"Q1179263":{"pageid":1190012,"ns":120,"title":"Item:Q1179263","lastrevid":69812790,"modified":"2026-04-13T09:33:31Z","type":"item","id":"Q1179263","labels":{"en":{"language":"en","value":"Efficiently solvable special cases of bottleneck travelling salesman problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 24172"}},"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":"Q1179263$9FB7615C-7F57-4FB1-A645-1A08FB77B61A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fcc69da0812ba03d9e4835b81ef2aedd20707e87","datavalue":{"value":{"text":"Efficiently solvable special cases of bottleneck travelling salesman problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179263$4DC2EE5C-2A9B-44EE-A8E2-40D39B164C3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2fccb9a9c9ab8cfcf136734667a4cafec4959e91","datavalue":{"value":"0747.90081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$3FE9C6E4-DDD4-4C2C-BA31-C488C3DFADED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"967f3509a5ea4241f4efedfd47d3387a20b765ae","datavalue":{"value":"10.1016/0166-218X(91)90024-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$6C7C6B44-9B4F-44E3-B53F-807CF2FA145C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6e30040f0ec4d6cb515b3b03961f5ab9c0b25f5","datavalue":{"value":{"entity-type":"item","numeric-id":1179262,"id":"Q1179262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$9C617678-A3A5-4B7F-88D4-B261B3EB462D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"666364d845a4821db20440b841f1ca6c219a6664","datavalue":{"value":{"entity-type":"item","numeric-id":170644,"id":"Q170644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$4F38F75A-D60F-4447-A07F-46B80F4A7A88","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":"Q1179263$E9A8CE86-120A-440D-A91E-33D2FC2C3480","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179263$5FD63F92-6A3B-4A2B-B8D6-961039925EB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f44f1d93327a98a1bed7a2dad7f82303723bd8e4","datavalue":{"value":"A special case of the bottleneck travelling salesman problem is investigated. For distance matrices that are circulant matrices, it is shown that the problem can be solved in \\(O(n \\log n)\\) time in contrast with the sum version of the problem for which this is still an open question. Sufficient conditions are then derived under which the optimal solution is a pyramidal tour. Some, but not all of these, are analogues of the same conditions for the sum version of the problem. Finally, the problem can be solved in \\(O(n \\log n)\\) time for cost matrices \\(c_{i,j}=a_ ib_ j\\) where \\(a_ 1\\leq a_ 2\\cdots\\) and \\(b_ 1\\geq b_ 2\\cdots\\). The solution is not always a pyramidal tour, in distinction with the sum version where this is always the case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179263$332FC96E-8D77-43C5-9060-606772CDBC07","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$480FC157-CA44-4E34-A33F-C592E8CBD43F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$C0BF415E-E480-4C99-850C-69F64CDAC563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$B4C5FD95-07D8-45AF-8C78-859528433880","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e85eafbd590ecd083a74af461d0cfa95e43f2e6","datavalue":{"value":"24172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$149F27D7-64A5-41F0-BF89-75B9F8B32D51","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"206e3090e495a35db9e8ea31ea8e33d01dfdde99","datavalue":{"value":"sufficient optimality conditions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179263$ED55F8E7-7C1C-49ED-8D3A-89522E9E71FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa757cda4dd5815e648a79afdbb25542015fb728","datavalue":{"value":"bottleneck travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179263$42BB5E7D-C3D8-4FA9-BFCA-569B2554037C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c608643b52d5e387c67f701068f700ba0b44ce3","datavalue":{"value":"pyramidal tour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179263$C88A1395-E660-41ED-9AF0-F5100FB95B43","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":"Q1179263$A4D3BD38-AE62-491A-96D5-0135CCF042BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f68b0326e7aa38abb9eeb18ed41ed621e88f616","datavalue":{"value":{"entity-type":"item","numeric-id":5643797,"id":"Q5643797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$FD5F50DB-78CB-4CA9-9093-8A1342916178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7592fae2ac5ee3a2f75ff1d9b8bed5d910038d4f","datavalue":{"value":{"entity-type":"item","numeric-id":4193256,"id":"Q4193256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$9520A552-2380-47FA-AB32-8318F7561C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd6a279d1befb0589112245619985670d218dd74","datavalue":{"value":{"entity-type":"item","numeric-id":3776619,"id":"Q3776619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$7899B477-B077-4177-84C5-6DCCB9E0A5AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de5e098f2b6e6238d033ffee7b1f35a44ae2bba","datavalue":{"value":{"entity-type":"item","numeric-id":4168391,"id":"Q4168391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$8F12E21A-4020-4D7D-A884-736FBA4816F7","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":"Q1179263$EC3EF2E8-1F3A-489D-82BB-BA220F065082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a2f68cf8007c4ac0704f6d68c007861325eaef2","datavalue":{"value":{"entity-type":"item","numeric-id":4127641,"id":"Q4127641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$00697687-9D46-49B6-A1B7-D70AED9EB77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc04c7e08b4611983e6b0576380f7c22d92c7a9","datavalue":{"value":{"entity-type":"item","numeric-id":5653802,"id":"Q5653802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$B78FF634-60E1-4452-9956-6FF61DFB3CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf1fb1d09ba244594c9367a1e4372305f09d58c2","datavalue":{"value":{"entity-type":"item","numeric-id":3932608,"id":"Q3932608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$7F104342-E8E2-4552-96F2-C3B594B53AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"956fb7987b24304176d3290e6e55a2428c6ae2ae","datavalue":{"value":{"entity-type":"item","numeric-id":768985,"id":"Q768985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179263$C37ECEEE-491A-484C-99B2-23D42D7DD381","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"54008658aa1dbda3491f10f5fb53e2b585a61403","datavalue":{"value":"https://doi.org/10.1016/0166-218x(91)90024-q","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179263$3ADBA50E-3EA1-4D70-9C1E-DFD313C13828","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99ba95820155a7e092f1182f271d0d364ceaf7c6","datavalue":{"value":"W1970388956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179263$F083C8FF-7DAA-4F46-9657-1BF266D9D3C1","rank":"normal"}],"P1643":[{"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":"5c65a93c31c688f67bd6b336a722be335ef18b78","datavalue":{"value":{"amount":"+0.8270582556724548","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":"Q1179263$520D0D3A-2ACD-452C-AE1D-BAF2A970D679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"add7f52dc1308ec8af56ee624fe7d193bd487c94","datavalue":{"value":{"entity-type":"item","numeric-id":1314323,"id":"Q1314323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd826e0c495688a74f9fad076b08181822b61c1d","datavalue":{"value":{"amount":"+0.7980266213417053","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":"Q1179263$B856197F-BB69-4BE7-97B6-8A07980D01B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"341456332366976cb4d850db4ef543cba3c11b3a","datavalue":{"value":{"entity-type":"item","numeric-id":1183480,"id":"Q1183480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f2e5e12ccd042791bef5cd16e53501fe168c72","datavalue":{"value":{"amount":"+0.7844559550285339","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":"Q1179263$5BB626A7-0DBD-4F76-928A-D57BD5CEE248","rank":"normal"},{"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":"50b814575f5c9d745c41db554c9511302834ba40","datavalue":{"value":{"amount":"+0.7799795866012573","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":"Q1179263$571C636C-3299-4CA0-A78C-D7F43CB62E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40b5cd46fff15dce15ee9da9cee4c02e93a0a59d","datavalue":{"value":{"entity-type":"item","numeric-id":3328310,"id":"Q3328310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"520f6406761a6e1c2715f23d8ddc069b929bcd0e","datavalue":{"value":{"amount":"+0.7774282693862915","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":"Q1179263$374B461E-17E8-46CF-8D61-175C37D80AB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficiently solvable special cases of bottleneck travelling salesman problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficiently_solvable_special_cases_of_bottleneck_travelling_salesman_problems"}}}}}