{"entities":{"Q1758845":{"pageid":1769587,"ns":120,"title":"Item:Q1758845","lastrevid":51598868,"modified":"2026-01-19T00:23:23Z","type":"item","id":"Q1758845","labels":{"en":{"language":"en","value":"A data-guided lexisearch algorithm for the bottleneck travelling salesman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6108286"}},"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":"Q1758845$32542127-3C39-4E10-A4B7-2D94DB596F5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bec4306021d4ad80dec308a078155129f07cebe9","datavalue":{"value":{"text":"A data-guided lexisearch algorithm for the bottleneck travelling salesman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1758845$9BA2F3AC-D996-4FBC-8186-DED481FBFB6D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b39b9a35cd6675099373bc7f90a6fc1ceaff36de","datavalue":{"value":"1254.90266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$AF300EA2-D05C-43B4-8A7E-EA8EF38471A0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d8b91ac1d45a5d5bb43aa9e91cf3bedecec5996","datavalue":{"value":"10.1504/IJOR.2011.041857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$EF6B1CFE-5841-4B58-A5AF-6942162955E8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"87225e7ef423c655f9581bcc86baaf99a56eef91","datavalue":{"value":{"entity-type":"item","numeric-id":410534,"id":"Q410534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758845$C2433064-B907-4FF8-9F8F-B5CF51E4712B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758845$62AD5945-5821-4C80-8A6D-AE26D74892E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"16d9ed1da0749c54273c05a4ba5499c71e474aeb","datavalue":{"value":{"time":"+2012-11-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1758845$19AAD79F-5811-4C41-9D35-7CEF91469633","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43db9732c6db22178ca7e94152307194422decdc","datavalue":{"value":"Summary: The bottleneck travelling salesman problem is to find a Hamiltonian circuit that minimises the maximum arc length in a graph. We first modify an existing lexisearch algorithm by incorporating good upper and lower bounds to obtain exact optimal solution to the problem. Then we present a data-guided lexisearch algorithm. Depending on the medians of rows of the cost matrix for the problem, the nodes of the network are renamed and a new alphabet table is constructed and then the modified lexisearch algorithm is applied. It is shown that this minor preprocessing of the data, before the lexisearch algorithm is applied, improves computational time substantially. The efficiency of our algorithms as against the existing lexisearch algorithm to the problem has been examined for some TSPLIB instances and a variety of randomly generated instances of different sizes and different types.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$6C26CDE0-CE00-4170-92E1-F0450C903468","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$5750FA3F-6424-4E9E-9C6C-E5D1CB024E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$C671417D-91A9-47D3-9E59-FFED20148395","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da3e5b09bdb8c209402bad7a97c0088d3518fdd1","datavalue":{"value":"6108286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$6CE359DC-A21D-4B06-BC06-C7BD8288B5FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa757cda4dd5815e648a79afdbb25542015fb728","datavalue":{"value":"bottleneck travelling salesman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$74446518-7E74-4A4B-84B6-FD4E1DD6C7BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$BE9B16CD-D9CE-4AB4-888A-A1DF1DBF7C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87b1445f21a754960c1f8704f1da6d7571086047","datavalue":{"value":"tour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$88EA83CE-AD8C-4A13-9D72-125E130A1180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b1183f7d6a6cdc5a0e6dbf043bfc0866a24315","datavalue":{"value":"alphabet table","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$87371725-FFB9-4956-9766-571DF6E05C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85e6d76da052d8250e99cae96c76aece3330b3dd","datavalue":{"value":"data-guided lexisearch","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$A3770C98-7BFC-4B25-A747-36373ECA31C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6906d309434fd0c76118d23a6a15594e9c5ca39","datavalue":{"value":"bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1758845$04A8E074-1365-4115-B0ED-A126ECCC644A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7237258b836283bef33e897e128d37db9d627348","datavalue":{"value":{"entity-type":"item","numeric-id":13727,"id":"Q13727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1758845$49B633F7-688D-4ADD-8E19-F468BB17E5E2","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":"Q1758845$EFC1E6B9-38AB-417F-8644-7C851F15CE5D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b54088a6481b476f802e231859a553b18079cc06","datavalue":{"value":"https://doi.org/10.1504/ijor.2011.041857","type":"string"},"datatype":"url"},"type":"statement","id":"Q1758845$A809C109-70B4-4FCE-8DDB-BB9B5A7B82AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98754651e94db1247711613941934a81f2875f50","datavalue":{"value":"W2149740490","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1758845$CB7D03EB-A36F-4948-B8AC-9910A7DA79E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ef8c6f24ce727687646e0b39d074d63d868ccc1","datavalue":{"value":{"entity-type":"item","numeric-id":410535,"id":"Q410535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"007df63440f152700073527c870eaf0a781f7747","datavalue":{"value":{"amount":"+0.8337581157684326","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":"Q1758845$9D9ED067-753D-4BD4-9677-1FB353E57CD9","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":"9b11aa5f0dc139c1b3d843015c5914a8f07b30fb","datavalue":{"value":{"amount":"+0.8206024169921875","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":"Q1758845$CEFA8F5C-5300-4A5E-ADF2-74FF614379D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"306b64ad72be68f677fb8ee5b4dfce074ac84dc3","datavalue":{"value":{"entity-type":"item","numeric-id":2269075,"id":"Q2269075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2a16718d23cb9f352c0006d753073bb09437204","datavalue":{"value":{"amount":"+0.7935695648193359","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":"Q1758845$218DDF1E-8EA4-48C6-BCDE-792A4D139196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6135721dbb3f3eeec8faaa50c76ea618cdc663eb","datavalue":{"value":{"entity-type":"item","numeric-id":519098,"id":"Q519098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dbb95ffb039bf8dcc64e4e7554a3618c4b9fe8f","datavalue":{"value":{"amount":"+0.7835323214530945","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":"Q1758845$79B5117A-18CF-406E-9CA7-D60186D54522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16839f8d7afa32e845d012089fba5eb0fe5c063e","datavalue":{"value":{"entity-type":"item","numeric-id":336878,"id":"Q336878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"746c00418548e8484c22483d384c43b570990b35","datavalue":{"value":{"amount":"+0.7520038485527039","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":"Q1758845$304AE24F-382B-472A-8DB7-49AF1ABE23F2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1758845","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1758845"}}}}}