{"entities":{"Q442933":{"pageid":444700,"ns":120,"title":"Item:Q442933","lastrevid":56906265,"modified":"2026-03-24T13:41:27Z","type":"item","id":"Q442933","labels":{"en":{"language":"en","value":"Hamiltonian paths in some classes of grid graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6063400"}},"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":"Q442933$C0222FE2-F058-4DB2-AA25-1E0827CE2CEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f970c30e1a124e74aa00e6a464bf1295b7c35fc","datavalue":{"value":{"text":"Hamiltonian paths in some classes of grid graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q442933$489E5217-5F18-4E91-9170-33B8E7E79663","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"acc27d8a5c66a59da192d9c01693016c40e8a136","datavalue":{"value":"1245.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$BBB40817-9B20-44CF-A238-D7C734C5CB21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7bfbff48f601d31ce6339edd923209aff1bc1a9","datavalue":{"value":"10.1155/2012/475087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$061C0C59-2263-4E25-A308-6DA335CE4E75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc01007b70edf502fef2e4d298a0f2efd27c1694","datavalue":{"value":{"entity-type":"item","numeric-id":248939,"id":"Q248939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$3EFF84FF-F793-4D6B-9FBD-608B7F60215B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e217e415ead226bb5d5fb4a8ddd5f183e260113","datavalue":{"value":{"entity-type":"item","numeric-id":248940,"id":"Q248940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$8A1451F9-142C-4368-8BBF-C34F530617A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$AC808035-A75A-4041-9B6E-B02949EF044E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6e1e94d61bf4c54e2ef7ef4c374530b93a773f9d","datavalue":{"value":{"time":"+2012-08-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":"Q442933$A74218C8-8032-4064-8777-B450C216FC32","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd19f5f856bc0896fc32eb3b00158a4d4a0bbd93","datavalue":{"value":"https://arxiv.org/abs/1107.1780","type":"string"},"datatype":"url"},"type":"statement","id":"Q442933$214969D4-FA02-4686-875B-801644529C4C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9aadfd4dfc99700bdf169e45a609732b1ca13e62","datavalue":{"value":"Summary: The Hamiltonian path problem for general grid graphs is known to be NP-complete. In this paper, we give necessary and sufficient conditions for the existence of Hamiltonian paths in \\(L\\)-alphabet, \\(C\\)-alphabet, \\(F\\)-alphabet, and \\(E\\)-alphabet grid graphs. We also present linear-time algorithms for finding Hamiltonian paths in these graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$2A605156-1963-4630-846C-627999DD5692","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$21F0738D-96F5-45FE-BB5F-9932204A0818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$E1F9BA92-6AFD-4765-AD64-6016A82FD3EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"53a2468a11faf5b79286e45abf75853579fc1eac","datavalue":{"value":"6063400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$19313A79-A709-4ADE-B740-58DD0F4BCA0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$3BAAACCE-1B1C-4309-B6C3-7CC28B10A021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0067024bd81469a455fea51d225272e35535db3c","datavalue":{"value":"\\(L\\)-alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$75A13E5F-288E-49E8-9800-946A9E357286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0dd90033cfed90fa7f97274b2b7121e158767a9","datavalue":{"value":"\\(C\\)-alphabet,","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$A278940B-BDC0-4ADD-814C-1C8A4A3ECDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aefd166ba3dee6b5acff544ea8284184255541fd","datavalue":{"value":"\\(F\\)-alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$461CC220-4363-459A-B180-4A3594A3037E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e7816c9ed70f051d81f0a032165bfa859112782","datavalue":{"value":"\\(E\\)-alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q442933$E519437B-9EE9-40E9-8DDE-F21903E4AD13","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a03565bf15ac2836869c3574cc8a09ac3ac8ab5c","datavalue":{"value":"Q58905946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$3FABA312-F76D-4066-84FA-1F223D74C88C","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":"Q442933$4CE7BD95-77EF-4C0C-8D11-6325B04FA61D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6de0a0f06f6555d28501824be8f0fe3d174512e8","datavalue":{"value":"W2023050191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442933$5909D87B-0123-4FEB-A4ED-0613AAD5A085","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6557be7f521c8adde3f7bef630a92c5b17b59491","datavalue":{"value":{"entity-type":"item","numeric-id":1589966,"id":"Q1589966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$DE23AF0F-2DD1-4E74-868A-B3F234324519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$0990BC82-5983-440A-833A-61C18EBA3B77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82040db26e41ad551b2b9ee4a805cebd408e2613","datavalue":{"value":{"entity-type":"item","numeric-id":1210553,"id":"Q1210553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$8F8F59B3-6F7F-4A5F-ADE3-C5A5708C9121","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":"Q442933$E2A330FB-57EA-4220-827B-EBFE856EEBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20715ecb87b5e0125fba913e88238b12429f64dc","datavalue":{"value":{"entity-type":"item","numeric-id":3801093,"id":"Q3801093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$FC5E80F0-A7ED-4963-B672-2E07651D5472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9257374932dc215b7fcefd8f7be7501d92172be","datavalue":{"value":{"entity-type":"item","numeric-id":1765415,"id":"Q1765415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$2BF5BF9B-B148-44DB-A70F-80EC1AFBB92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3536b0164eb37d12e083d9dfc12450bc92abfda","datavalue":{"value":{"entity-type":"item","numeric-id":1041720,"id":"Q1041720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$01A05C9E-8B90-4DD6-848D-45AE9F51C7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa97f0110ceefce3316c5fbe9c21778948ad688","datavalue":{"value":{"entity-type":"item","numeric-id":4742820,"id":"Q4742820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$212A7282-6A59-40B4-B29E-B09085CE1E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa08a9b1498c1f91355fe2a62d9ed04ec18311c3","datavalue":{"value":{"entity-type":"item","numeric-id":4030195,"id":"Q4030195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$7E1D156D-DADE-4735-B18B-7CADCDF0E4B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e42b2a75729859b1a2e18c0934e8b5d43319a18b","datavalue":{"value":{"entity-type":"item","numeric-id":1614877,"id":"Q1614877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$AEA00DCF-1ED8-4540-B215-CC8FCC2A5D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cecbd638843686db968440dc0ca944ee5c03f9f6","datavalue":{"value":{"entity-type":"item","numeric-id":998354,"id":"Q998354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$A23FE92E-DD2E-45BC-9E16-8D5CF5366CB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0068ec9c873a41716c92fa8f8e8e5308d08a5cb0","datavalue":{"value":{"entity-type":"item","numeric-id":627140,"id":"Q627140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$3B1175E5-B9E3-40AF-B26C-2E2F952A9115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"191faf59ae0d0410cb9e3a7811877e77543d0c70","datavalue":{"value":{"entity-type":"item","numeric-id":765359,"id":"Q765359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$152FEC17-FE6D-4163-ABB7-319CE0095341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae40028ec83f5cc9dae093338b534dc37b666e8","datavalue":{"value":{"entity-type":"item","numeric-id":442933,"id":"Q442933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442933$5DE83A8C-3218-414C-AC76-79BCD7027083","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a4aab1cfe520622545e34d42deb17f7f7784e37","datavalue":{"value":{"entity-type":"item","numeric-id":5964021,"id":"Q5964021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be5bd3a1e0abdd83748343858eccbc5c4ad65e8","datavalue":{"value":{"amount":"+0.9591383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$4B5E796A-682C-4B31-B555-78650C171DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19964024d937dba5536ca86250cc49772f62f4a1","datavalue":{"value":{"entity-type":"item","numeric-id":4030195,"id":"Q4030195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15bb80fdc4dfb512c312cbad0cf4fd54e19844fb","datavalue":{"value":{"amount":"+0.9381809","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$4D8E866A-5F4F-4E8E-BA4A-E9A5A40C39AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bca45e2cdd286c119d146f3406df42e9c5b03d4c","datavalue":{"value":{"entity-type":"item","numeric-id":3772257,"id":"Q3772257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f13ae73551568304f762ba8edd913193afdde4d","datavalue":{"value":{"amount":"+0.9360149","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$FDB2CDF7-20F1-4508-A86A-42D2005E0932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16ad9193795738d46743cbd99b24d17e7379a6d7","datavalue":{"value":{"entity-type":"item","numeric-id":3819098,"id":"Q3819098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea5320d68f4fe5eb800c143c1cdeb984244f4ddd","datavalue":{"value":{"amount":"+0.93376046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$5C57DB69-841E-4468-B165-C9C54173B637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc2ebf8b2fd584b0991d8ca46d65ad06c40173c9","datavalue":{"value":{"entity-type":"item","numeric-id":1309475,"id":"Q1309475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c4b569e7ce37f1e4f2bed87f7e4eb1173969ad8","datavalue":{"value":{"amount":"+0.92975134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$7A45235E-47FF-45E4-A9A4-A7CA681FC5EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d777c5f7680a03db1adac4d05d8723c218933dd","datavalue":{"value":{"entity-type":"item","numeric-id":3167351,"id":"Q3167351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b9789fd3dd7401843edc2953877dbcf418c3c7d","datavalue":{"value":{"amount":"+0.9258347","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$AA0E2C4D-A240-45E4-BACE-FBD01EF756D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74c9382efd3b67a2f91835ab5b84a0c04e97ae06","datavalue":{"value":{"entity-type":"item","numeric-id":5488886,"id":"Q5488886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52fea5cc508795409393f0da0c50d99604fc35e0","datavalue":{"value":{"amount":"+0.9248952","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$FF707015-86D8-477E-B039-2882B93CC20B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e1efe3469dbf4d1d1525643698f920cde3c5821","datavalue":{"value":{"entity-type":"item","numeric-id":1044918,"id":"Q1044918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3eabcfc777ecc5eadc45baed35ad9181ec56f9c","datavalue":{"value":{"amount":"+0.92105365","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$C2C40D61-F906-43D9-B822-C139CAB0F21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ac7a0b23f234d294e9e881bf1937522eec54ced","datavalue":{"value":{"entity-type":"item","numeric-id":745636,"id":"Q745636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93fde22d4f34899f97baadf5316a843b52fb2dd1","datavalue":{"value":{"amount":"+0.92051053","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442933$88D01277-F354-4F46-A8E8-E58732265549","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":"Q442933$11F0673B-6F74-449F-BF64-4E3BFE162931","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:442933","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:442933"}}}}}