{"entities":{"Q1722882":{"pageid":1733623,"ns":120,"title":"Item:Q1722882","lastrevid":68906673,"modified":"2026-04-13T03:01:47Z","type":"item","id":"Q1722882","labels":{"en":{"language":"en","value":"HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7024766"}},"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":"Q1722882$F6B84428-D0B9-4466-949F-7A8492079F05","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55e055f355147438bb354a88f582e447ebb6eaad","datavalue":{"value":{"text":"HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1722882$5B49C89D-882B-4388-8BBB-06F4C3FD9088","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2d41377375c833c31c7925631397b990b8988152","datavalue":{"value":"1460.05182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$0F190021-6FE4-4578-9BCB-E9D37F4ADB20","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6165fc1de16b75264c335040d9a80d9fb59c90e3","datavalue":{"value":"10.1155/2018/9328103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$6465D72C-5AE9-4D96-99EC-695FADFCF460","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0783a657ff9ee6f96b99e4ca95d9c836a5c394c","datavalue":{"value":{"entity-type":"item","numeric-id":1722881,"id":"Q1722881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$66023151-1012-4874-AEE0-2D76BDD2F5AD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"362619d6d72cefeadaf5f0a564d98a756a56828c","datavalue":{"value":{"entity-type":"item","numeric-id":896724,"id":"Q896724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$5F0F5FE8-1D26-4125-B888-184B7EABBBE6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0e07e584aaf32d9a9691066d4a126742d1828198","datavalue":{"value":{"time":"+2019-02-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1722882$B356314C-663E-4084-9714-CA3AE660F992","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0de41ec8a9bb782b4ce16a2495da63a6889e2a3f","datavalue":{"value":"Summary: Hamiltonian Cycle Problem is one of the most explored combinatorial problems. Being an NP-complete problem, heuristic approaches are found to be more powerful than exponential time exact algorithms. This paper presents an efficient hybrid heuristic that sits in between the complex reliable approaches and simple faster approaches. The proposed algorithm is a combination of greedy, rotational transformation and unreachable vertex heuristics that works in three phases. In the first phase, an initial path is created by using greedy depth first search. This initial path is then extended to a Hamiltonian path in second phase by using rotational transformation and greedy depth first search. Third phase converts the Hamiltonian path into a Hamiltonian cycle by using rotational transformation. The proposed approach could find Hamiltonian cycles from a set of hard graphs collected from the literature, all the Hamiltonian instances (1000 to 5000 vertices) given in TSPLIB, and some instances of FHCP Challenge Set. Moreover, the algorithm has O(n) worst case time complexity. The performance of the algorithm has been compared with the state-of-the-art algorithms and it was found that HybridHAM outperforms others in terms of running time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1722882$B2AE5048-417A-4422-B476-A264FB53EFF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$A4E2165E-08EF-4F2C-8A82-021616640756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$E47475CA-9D91-422C-999A-BDA9E64FA8D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e187790aac124a227a61c7f68a6d0bc97c8ab4d","datavalue":{"value":"7024766","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$0B7267DA-648E-4135-85B2-625A11D449C1","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"47e4fed8534c7da3857b9a942e120c00af73a3c1","datavalue":{"value":{"entity-type":"item","numeric-id":16903,"id":"Q16903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$AC0F953A-53F0-463D-9928-97F6CD26C0C2","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":"Q1722882$361BA144-4992-4C7A-B88A-D14E1440B781","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f8669574d21f0e6ad08f279f673b05ce3cf7afc","datavalue":{"value":"https://doi.org/10.1155/2018/9328103","type":"string"},"datatype":"url"},"type":"statement","id":"Q1722882$AFEB6725-F85F-40E4-860D-17CC74DA4537","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d831b93f9cdae36119f84acd95981a41ec5bab5e","datavalue":{"value":"W2896581360","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1722882$5D343AE9-9FBC-4FCD-9F94-E29F2C6D0BA2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$E1AEE44B-7BAA-4E00-A7D2-9C8C90C5BCD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0d9c586ef9cf53af881c9950417cc5b66679aa","datavalue":{"value":{"entity-type":"item","numeric-id":3264678,"id":"Q3264678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$0069141D-AEB1-4024-B083-6CD903A9A49F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0af97c5d1309395cd1a0cc77b905a28027b1e02d","datavalue":{"value":{"entity-type":"item","numeric-id":801082,"id":"Q801082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$8B5B23ED-EDF1-41B4-9F38-93E95B7144E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7a5eb340b9a0ad49d64cfad16253cbcf6809378","datavalue":{"value":{"entity-type":"item","numeric-id":1396651,"id":"Q1396651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$375F7EB7-B134-4902-9AF2-DCB071AF29A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa748eaf541ef47b9bc5728b38f8d3e305bac1d","datavalue":{"value":{"entity-type":"item","numeric-id":4044618,"id":"Q4044618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$1B3C5361-3BAD-4FD5-8452-5C01881FBEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab4410bd85ba93ca8638378f859367903f5b9ff0","datavalue":{"value":{"entity-type":"item","numeric-id":4083324,"id":"Q4083324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$BE1C293B-30D4-452C-A381-CFDDF13545D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea3d52b4bcdccd9b4df81c41bc9dba487c597cee","datavalue":{"value":{"entity-type":"item","numeric-id":1197026,"id":"Q1197026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$501C9F29-48D1-4367-BE97-692F6D4E1412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd78c9177f33d42f4e779883ac511777364d275","datavalue":{"value":{"entity-type":"item","numeric-id":4749863,"id":"Q4749863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$9E2600C1-0316-4194-9252-C41C24818CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f638163b3cd2494ce14de2e941b1965b451aaf65","datavalue":{"value":{"entity-type":"item","numeric-id":2495226,"id":"Q2495226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$62AF565D-6585-43CE-BA8D-1EA85B6BCCFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c65e5b083f4f44d31025fb954ea1b19f8a45c8ad","datavalue":{"value":{"entity-type":"item","numeric-id":1223313,"id":"Q1223313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$C4CB084D-6D3A-4D66-9786-FAE0B4948F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf9134e33ec7d5eec841c137750aba56352f9a35","datavalue":{"value":{"entity-type":"item","numeric-id":1099190,"id":"Q1099190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$A88348F1-1298-4163-95F3-37D33C7BF270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da09e828a82eb4a71d697ef2b9c6f1e3c9b51a54","datavalue":{"value":{"entity-type":"item","numeric-id":3790664,"id":"Q3790664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$87BFCFB5-513B-4738-8006-C68490372296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1702708bfd22055c31f8fdc88a657f52d9db0c91","datavalue":{"value":{"entity-type":"item","numeric-id":4306372,"id":"Q4306372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$BE575398-D420-439A-A5D2-C8F62C87BAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5748fdf067df37ed0440dcde76cd63cc6650111f","datavalue":{"value":{"entity-type":"item","numeric-id":1092923,"id":"Q1092923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$405D8E6C-031C-45F0-9A30-87C481EC8A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0930d57b126d4670b8351b41154baa4cb1f96e2","datavalue":{"value":{"entity-type":"item","numeric-id":5671788,"id":"Q5671788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$9FD7E51F-DA50-4EB7-BEEA-355CF91CD221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b68a7770c22a08c819d0c75c3b070742efa76ba4","datavalue":{"value":{"entity-type":"item","numeric-id":1584821,"id":"Q1584821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$6891640C-D7F3-4CC7-B021-FB4FAF85EEE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c85ad1c11b4c2c66512da23bc9ecc32c36b4a62","datavalue":{"value":{"entity-type":"item","numeric-id":5510390,"id":"Q5510390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$1644E2B8-5421-4A03-9907-1F803B8542D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f925aefd9c962b62195e63bd5ee29583f160cfe","datavalue":{"value":{"entity-type":"item","numeric-id":5378674,"id":"Q5378674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$EBB61CB2-0E59-46A7-9210-EF9728DCD6C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54cd3aa9cd5c5f629ee7f89d5314f4fed9b89aa0","datavalue":{"value":{"entity-type":"item","numeric-id":744218,"id":"Q744218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$311832BC-84A6-471F-8094-7A82CBDC5B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97abe184fd6229f81a5772c85c011e02a9e90ce","datavalue":{"value":{"entity-type":"item","numeric-id":5376425,"id":"Q5376425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$02583AA2-0C3E-42FF-B0BA-3C28520A2542","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be4cb8942958ad2bff96ac6d4bb3f875ba7092e3","datavalue":{"value":{"entity-type":"item","numeric-id":666352,"id":"Q666352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faf109b11b9022553d92c47dc5e60c5f1ad66f8e","datavalue":{"value":{"amount":"+0.8056302070617676","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":"Q1722882$643F7DF8-E266-48AD-8325-1D4F1FEF70C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23d80691450a10d98e3a4381ce7401da1b1a3eff","datavalue":{"value":{"entity-type":"item","numeric-id":744218,"id":"Q744218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c623a539d71ae6606bd754d6b12832867bcd24a","datavalue":{"value":{"amount":"+0.787720263004303","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":"Q1722882$F7D4E48A-C8AE-4CEF-8B1F-4497B1E81A62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b27b7353e20aba23aa89a8ecef970fee6145b437","datavalue":{"value":{"entity-type":"item","numeric-id":4204017,"id":"Q4204017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6af545662851e2835d8116ad9213e08b2c60758","datavalue":{"value":{"amount":"+0.7721896767616272","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":"Q1722882$B5F9434D-3C8A-4930-A2B0-9A855517D885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceabe4942b2e51efcb390b534644893f9f753a24","datavalue":{"value":{"entity-type":"item","numeric-id":1099190,"id":"Q1099190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f32a7c877fa13416b8332c483836d93d2f5b591e","datavalue":{"value":{"amount":"+0.7565357685089111","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":"Q1722882$9B2C3118-65AD-4842-B703-5A8A47057FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5b97d24b8ff7d8ee3b4d1815349597e2cb40e88","datavalue":{"value":{"entity-type":"item","numeric-id":2963159,"id":"Q2963159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1383470fe9a73d325d929d81c7fc2774ec42e517","datavalue":{"value":{"amount":"+0.7561339139938354","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":"Q1722882$68B325E9-9849-435B-B983-C663197CED2F","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1722882$B0D270AB-C919-4060-9EC6-6F0E387E8BBD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/HybridHAM:_a_novel_hybrid_heuristic_for_finding_Hamiltonian_cycle"}}}}}