1. STORRE
  2. Faculty of Natural Sciences
  3. Computing Science and Mathematics
  4. Computing Science and Mathematics Conference Papers and Proceedings
Please use this identifier to cite or link to this item: http://hdl.handle.net/1893/34655
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSleegers, Joerien_UK
dc.contributor.authorThomson, Sarah Len_UK
dc.contributor.authorVan Den Berg, Daanen_UK
dc.contributor.editorBäck, Thomasen_UK
dc.contributor.editorvan Stein, Basen_UK
dc.contributor.editorWagner, Christianen_UK
dc.contributor.editorGaribaldi, Jonathanen_UK
dc.contributor.editorLam, H.K.en_UK
dc.contributor.editorCottrell, Marieen_UK
dc.contributor.editorDoctor, Faiyazen_UK
dc.contributor.editorFilipe, Joaquimen_UK
dc.contributor.editorWarwick, Kevinen_UK
dc.contributor.editorKacprzyk, Januszen_UK
dc.date.accessioned2022-11-11T01:02:06Z-
dc.date.available2022-11-11T01:02:06Z-
dc.date.issued2022en_UK
dc.identifier.urihttp://hdl.handle.net/1893/34655-
dc.description.abstractIn 2021, evolutionary algorithms found the hardest-known yes and no instances for the Hamiltonian cycle problem. These instances, which show regularity patterns, require a very high number of recursions for the best exact backtracking algorithm (Vandegriend-Culberson), but don't show up in large randomized instance ensembles. In this paper, we will demonstrate that these evolutionarily found instances of the Hamiltonian cycle problem are hard for all major backtracking algorithms, not just the Vandegriend-Culberson. We compare performance of these six algorithms on an ensemble of 91,000 randomized instances plus the evolutionar-ily found instances. These results present a first glance at universal hardness for this NP-complete problem. Algorithms, source code, and input data are all publicly supplied to the community.en_UK
dc.language.isoenen_UK
dc.publisherSCITEPRESS – Science and Technology Publicationsen_UK
dc.relationSleegers J, Thomson SL & Van Den Berg D (2022) Universally Hard Hamiltonian Cycle Problem Instances. In: Bäck T, van Stein B, Wagner C, Garibaldi J, Lam H, Cottrell M, Doctor F, Filipe J, Warwick K & Kacprzyk J (eds.) <i>Proceedings of the 14th International Joint Conference on Computational Intelligence - ECTA</i>. ECTA 2022 : 14th International Conference on Evolutionary Computation Theory and Applications, Valletta, Malta, 24.10.2022-26.11.2022. SCITEPRESS – Science and Technology Publications, pp. 105-111. https://doi.org/10.5220/0011531900003332en_UK
dc.rightsThis paper is licenced under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Licence (CC BY-NC-ND - https://creativecommons.org/licenses/by-nc-nd/4.0/)en_UK
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/en_UK
dc.subjectExact Algorithmsen_UK
dc.subjectInstance Hardnessen_UK
dc.subjectEvolutionary Algorithmsen_UK
dc.subjectPhase Transitionen_UK
dc.titleUniversally Hard Hamiltonian Cycle Problem Instancesen_UK
dc.typeConference Paperen_UK
dc.identifier.doi10.5220/0011531900003332en_UK
dc.citation.issn2184-2825en_UK
dc.citation.spage105en_UK
dc.citation.epage111en_UK
dc.citation.publicationstatusPublisheden_UK
dc.type.statusVoR - Version of Recorden_UK
dc.author.emails.l.thomson@stir.ac.uken_UK
dc.citation.btitleProceedings of the 14th International Joint Conference on Computational Intelligence - ECTAen_UK
dc.citation.conferencedates2022-10-24 - 2022-11-26en_UK
dc.citation.conferencelocationValletta, Maltaen_UK
dc.citation.conferencenameECTA 2022 : 14th International Conference on Evolutionary Computation Theory and Applicationsen_UK
dc.citation.date26/10/2022en_UK
dc.citation.isbn978-989-758-611-8en_UK
dc.contributor.affiliationIndependenten_UK
dc.contributor.affiliationComputing Science and Mathematics - Divisionen_UK
dc.contributor.affiliationVrije University Amsterdamen_UK
dc.identifier.wtid1852810en_UK
dc.contributor.orcid0000-0001-6971-7817en_UK
dc.date.accepted2022-08-05en_UK
dcterms.dateAccepted2022-08-05en_UK
dc.date.filedepositdate2022-11-03en_UK
rioxxterms.apcnot requireden_UK
rioxxterms.typeConference Paper/Proceeding/Abstracten_UK
rioxxterms.versionVoRen_UK
local.rioxx.authorSleegers, Joeri|en_UK
local.rioxx.authorThomson, Sarah L|0000-0001-6971-7817en_UK
local.rioxx.authorVan Den Berg, Daan|en_UK
local.rioxx.projectInternal Project|University of Stirling|https://isni.org/isni/0000000122484331en_UK
local.rioxx.contributorBäck, Thomas|en_UK
local.rioxx.contributorvan Stein, Bas|en_UK
local.rioxx.contributorWagner, Christian|en_UK
local.rioxx.contributorGaribaldi, Jonathan|en_UK
local.rioxx.contributorLam, H.K.|en_UK
local.rioxx.contributorCottrell, Marie|en_UK
local.rioxx.contributorDoctor, Faiyaz|en_UK
local.rioxx.contributorFilipe, Joaquim|en_UK
local.rioxx.contributorWarwick, Kevin|en_UK
local.rioxx.contributorKacprzyk, Janusz|en_UK
local.rioxx.freetoreaddate2022-11-10en_UK
local.rioxx.licencehttp://creativecommons.org/licenses/by-nc-nd/4.0/|2022-11-10|en_UK
local.rioxx.filename2022Sleegersetal-UniversallyHardHamiltonianCycleProblemInstances.pdfen_UK
local.rioxx.filecount1en_UK
local.rioxx.source978-989-758-611-8en_UK
Appears in Collections:Computing Science and Mathematics Conference Papers and Proceedings

Files in This Item:
File Description SizeFormat 
2022Sleegersetal-UniversallyHardHamiltonianCycleProblemInstances.pdfFulltext - Published Version949.89 kBAdobe PDFView/Open


This item is protected by original copyright

View License
Show simple item record


A file in this item is licensed under a Creative Commons License Creative Commons

Items in the Repository are protected by copyright, with all rights reserved, unless otherwise indicated.

The metadata of the records in the Repository are available under the CC0 public domain dedication: No Rights Reserved https://creativecommons.org/publicdomain/zero/1.0/

If you believe that any material held in STORRE infringes copyright, please contact library@stir.ac.uk providing details and we will remove the Work from public display in STORRE and investigate your claim.