{"entities":{"Q1917249":{"pageid":1927991,"ns":120,"title":"Item:Q1917249","lastrevid":69297588,"modified":"2026-04-13T06:04:30Z","type":"item","id":"Q1917249","labels":{"en":{"language":"en","value":"Finding Hamiltonian cycles in Delaunay triangulations is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 897363"}},"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":"Q1917249$57B923BB-9ED3-4615-A466-8E4A1CB8AA1D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a764976afcc1a8ed2ca472db9cbf14ef5d120f39","datavalue":{"value":{"text":"Finding Hamiltonian cycles in Delaunay triangulations is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1917249$EBAF7F9E-C94A-4BD5-B624-FE9BFAF2EB24","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"636ce4e519c336027d179e00f2854070f6452bf8","datavalue":{"value":"0852.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$9DBB9E4A-8696-40CF-8D60-8483FC001290","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ccbb489550c2068a23d4d49749389056d3a41958","datavalue":{"value":"10.1016/0166-218X(94)00125-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$08D4472D-28FF-4003-8555-E1264D467AB9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a35b6403677dee48292ada35d89e01ed621942c7","datavalue":{"value":{"entity-type":"item","numeric-id":803160,"id":"Q803160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$F59317BD-BA7F-4D15-882B-FAD309E6036C","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":"Q1917249$9C4B9728-60C4-4FAF-8DD2-22A4FA2E5D94","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d27590c3180a6d5205c0e1de015d26a216b7a32","datavalue":{"value":{"time":"+1996-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1917249$D7A73C49-2474-4DFB-8A12-82F7D60A74A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e5a03d4ec7c2308b5cb7c289f96454880e450f6d","datavalue":{"value":"It is shown that it is an NP-complete problem to determine whether a nondegenerate Delaunay triangulation or an inscribable polyhedron has a Hamiltonian cycle. There are also constructed a nondegenerate Delaunay triangulation and a simplicial, inscribable polyhedron, without 2-factors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$2C131D4A-DFA4-4407-B4E2-B32CA1B1D710","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8146f5feb228c23e2fa6738cca425f9e847fc191","datavalue":{"value":{"entity-type":"item","numeric-id":335340,"id":"Q335340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$D494E88C-AAC1-455C-9BF7-53F06FA14DF7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$29D08273-8236-4720-90B4-E53F2CB32FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$E674CE45-06B2-49B8-BE60-E08FEF07AC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$152CB35D-A26A-4B4C-9465-69EC4EF8F1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$9277CE58-EFE5-4741-AB36-5A3B8804BA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$74AB96B5-FD97-4C86-B5D1-88A4E8313CC2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04b39b6efcdddcfeaa8abb95bac18c7f9c601c5f","datavalue":{"value":"897363","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917249$306E374E-EC08-4C0B-B82F-2A921D8AB4E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$A7D265D5-5AC5-4DB6-8BD1-3F57FA28E40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5edfd6368999620c7e10cbba2e058c2b660abfd0","datavalue":{"value":"Delaunay triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$D457EB85-F09A-4B7B-B92C-7E9F0C682FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72cfe8b6e23f1592e04c00817e2191401b13b5ca","datavalue":{"value":"inscribable polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$5AE29F1D-9A1C-4B19-A4FF-80D03C494A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$B4F3CE01-5194-4625-AE0C-354F18E6DAA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9968ec4e808bb8307b76ccf4792fe2f300abe313","datavalue":{"value":"2-factors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917249$2232A29A-8270-4394-92FE-15AD5163C557","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":"Q1917249$B7199B2E-FF51-4C22-BD94-BECDD28FC403","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db695381606ba322df78c7a9c05e7660a22ed7b4","datavalue":{"value":{"entity-type":"item","numeric-id":3888545,"id":"Q3888545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$535BC58C-803D-44D5-B44E-4EDF12069E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$8A525587-32F5-476A-9DE4-6C678D53F564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cd35177b9fbbefa725a3537ebfd136511c156e","datavalue":{"value":{"entity-type":"item","numeric-id":1135110,"id":"Q1135110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$5595AAED-CBCF-4464-A3B9-55B0E5EFCE6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79b2cd01bd8642a86b4a476512521b17956a3210","datavalue":{"value":{"entity-type":"item","numeric-id":3689218,"id":"Q3689218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$6372A3BA-91A1-4561-A4FE-C3D6117C7A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95bb5094c069836073bea29b31b13fa3e847d9ea","datavalue":{"value":{"entity-type":"item","numeric-id":916416,"id":"Q916416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$0AF75AF7-6B4E-4556-965A-3A3D2D8FC7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bccf08a865eeb9947c0be6a909c2bddf0367f253","datavalue":{"value":{"entity-type":"item","numeric-id":2367404,"id":"Q2367404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$DD9AD178-CE72-4A8E-A243-D2DEFEF53DAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6adc929407b8a622b2a43e1c60f54bc723bafb7","datavalue":{"value":{"entity-type":"item","numeric-id":5573028,"id":"Q5573028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$8D0E2A35-B7AF-49D8-B3B8-9EA18295AF6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dc7886a3eb79e09c6d303af020736df228fc3d7","datavalue":{"value":{"entity-type":"item","numeric-id":1108041,"id":"Q1108041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$26A0E453-765D-40A7-8902-355CAF28BFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c62c0aea487917e321066ae8e083ef349f659a3c","datavalue":{"value":{"entity-type":"item","numeric-id":1122592,"id":"Q1122592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$9B036ED1-16DF-4568-AEC8-8CB5ABCF27AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db428495316d6ae753e706d4dcd25159b9fab95c","datavalue":{"value":{"entity-type":"item","numeric-id":4206767,"id":"Q4206767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$F64FDEE3-0818-4FAE-AF8C-4E18B2E548A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f411bd9dc7bed125bf4c6810bed2b15beb303e50","datavalue":{"value":{"entity-type":"item","numeric-id":803161,"id":"Q803161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$43FE9406-C305-41BA-902D-545D591AC167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"635e179f104df43c07c39243b0374fb69763997d","datavalue":{"value":{"entity-type":"item","numeric-id":1356410,"id":"Q1356410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$1209D842-C41C-418E-BDCC-F914C8FB70F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25b026e498c7466f890693e678f90760ff4b1c4e","datavalue":{"value":{"entity-type":"item","numeric-id":3772828,"id":"Q3772828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$06B7D432-4159-4618-AE6E-F6B43A63C4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ea635f94e2b65f62b69c801f434d265f9631766","datavalue":{"value":{"entity-type":"item","numeric-id":4020141,"id":"Q4020141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$7AAED0B5-C69C-42F8-9F19-020C38A8DFAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a74668e077023b019771a1a7d5a132cfdf00221","datavalue":{"value":{"entity-type":"item","numeric-id":1055435,"id":"Q1055435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$2A399007-118D-4274-A993-0937517B8125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03ef59651e35bf41cb57e133c2cbc976402fae58","datavalue":{"value":{"entity-type":"item","numeric-id":911313,"id":"Q911313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$F51644F0-9110-4A6E-AB40-E0D048A3A9B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea9afe4e4931055e4883da4f1437276841fe9c5f","datavalue":{"value":{"entity-type":"item","numeric-id":4763337,"id":"Q4763337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$B503AB39-834A-4F0F-AB1E-277EEA58E8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c450c2060f89e197a87ec2db0ecb4733b3e53b3","datavalue":{"value":{"entity-type":"item","numeric-id":1101225,"id":"Q1101225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$F1B30416-FD4B-47F0-BD97-40EF94ECDEF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46922753362575a6fb809bcfc673ff1c32b6470e","datavalue":{"value":{"entity-type":"item","numeric-id":5528475,"id":"Q5528475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$5902F6D8-F814-4F9A-9C4A-73C4B04B74F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fdd2700ef07980ab37c24485b8aed5f9da477e1","datavalue":{"value":{"entity-type":"item","numeric-id":3805971,"id":"Q3805971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$1D0CF3C8-5917-4385-8473-91EA2CCB7467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$A741221A-4C65-4E49-BAD2-1A09408C3D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16104bd8341cb98b36b8cf7d981483b5c2385915","datavalue":{"value":{"entity-type":"item","numeric-id":4030791,"id":"Q4030791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$7FE03012-A0F5-4C61-AF24-FD8FA25FDED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac19d26a25d596c0eb1b370a7ce00f7da1de8e2b","datavalue":{"value":{"entity-type":"item","numeric-id":2367216,"id":"Q2367216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$A1BFE5C1-E121-4D8D-B882-BE84426A988A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d1202d655c34fcad732b5b8e51d5613d9e296ce","datavalue":{"value":{"entity-type":"item","numeric-id":1333330,"id":"Q1333330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$6505FFC0-EE65-4D0E-A948-061FA125F13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871d64f8f68e934432c6eb622165ad15a02efbb6","datavalue":{"value":{"entity-type":"item","numeric-id":5902601,"id":"Q5902601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$E7B7592D-1A3B-454D-8392-757F3D01EF9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3fb5f043baeb68cce6e45f22256fe3a039c78a8","datavalue":{"value":{"entity-type":"item","numeric-id":5816402,"id":"Q5816402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$2122C277-94D7-4D64-B470-58BE6B5A2151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e433882c660a8e8d06ac4719241565d5c33a0d4b","datavalue":{"value":{"entity-type":"item","numeric-id":3231816,"id":"Q3231816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917249$2A0EFFF3-6523-4CA6-9CFC-0307DF3FD593","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f504c8f00ce793d87adcb18133359a1b00aba8c3","datavalue":{"value":{"entity-type":"item","numeric-id":916416,"id":"Q916416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ce2d91f868af0f632238ab3d8310ebf1d3d5ab6","datavalue":{"value":{"amount":"+0.7762501239776611","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":"Q1917249$D0AAC18D-5A19-4DF1-96D8-032A35460324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"688f876680392f263b7884961cfe6e7889e1b9c4","datavalue":{"value":{"entity-type":"item","numeric-id":1341680,"id":"Q1341680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee7b57b883222c9d5f17180b4aad6be6e523847f","datavalue":{"value":{"amount":"+0.7710272669792175","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":"Q1917249$2815C0BE-E98F-410C-AA19-E567F446AA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b1c6579fc747fedc5770ed2816f7d0653d05a0e","datavalue":{"value":{"entity-type":"item","numeric-id":1325240,"id":"Q1325240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50ac6ea599a8e88310f657151d8407c1f643288f","datavalue":{"value":{"amount":"+0.7679218649864197","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":"Q1917249$1D2061DC-1EE3-45F3-9033-9F01AF3B5EE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f4142bd5117020d9be2f6073ef9e6e1e078e22f","datavalue":{"value":{"entity-type":"item","numeric-id":803161,"id":"Q803161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1b14c4288755e192614a1bd9f18fd038436558","datavalue":{"value":{"amount":"+0.7569814324378967","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":"Q1917249$5E4FB191-2B57-46F6-9F81-0294C7D935DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding Hamiltonian cycles in Delaunay triangulations is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_Hamiltonian_cycles_in_Delaunay_triangulations_is_NP-complete"}}}}}