{"entities":{"Q788489":{"pageid":790337,"ns":120,"title":"Item:Q788489","lastrevid":64342644,"modified":"2026-04-11T19:13:01Z","type":"item","id":"Q788489","labels":{"en":{"language":"en","value":"A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3843136"}},"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":"Q788489$F3A1F1AE-C8C9-403E-A555-C2976D839756","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4a9ba0c8f0c81cc27c0718d661bab5a04349ce6","datavalue":{"value":{"text":"A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q788489$A71F6FF1-997E-440A-BB68-154B05BEFF06","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fe4b7827a8221e4bdd85dd0e7305d0d005e3f48","datavalue":{"value":"0531.68008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$2BE4F794-22EF-40D4-9CF3-A2261D378F2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"63a49879c4ffc7ddbf3a527ae3eed6221c6396f2","datavalue":{"value":"10.1016/0166-218X(84)90109-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$632AB22D-0CE2-4709-A3E2-E9D30336B743","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0608c28dd6e3edb1ad2e60313b9ab4c48668656b","datavalue":{"value":{"entity-type":"item","numeric-id":406636,"id":"Q406636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$EA79CA49-4AE0-421B-A5A6-9D4A5B07CA66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de6973bce00d7734584bdd4f2276aa6c7a6f56f7","datavalue":{"value":{"entity-type":"item","numeric-id":788487,"id":"Q788487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$67D1A9AE-4D4F-49C0-87B2-6D86BCAE1D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d6129f2694707a8dc943ba2b6db8331eade716e","datavalue":{"value":{"entity-type":"item","numeric-id":788488,"id":"Q788488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$8DD3E230-B4A0-4793-8422-2A7BCA1CD4F3","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":"Q788489$F7574D41-1C39-48FE-8C17-14E685E12FDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q788489$D7F275CB-7373-42BD-A510-82362668A705","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8add5497235d1e75efc93d22e3b3f4488e0f4cda","datavalue":{"value":"The Hamiltonian cycle problem is a well-known NP-complete problem. Some restrictions of this problem, even for planar graphs, remain NP-complete while other subclasses possess polynomial-time algorithms. The authors consider the class of 4-connected maximal planar graphs. Using a slight modification of Whitney's theorem [\\textit{H. Whitney}, Ann. Math., II. Ser. 32, 378-390 (1931; Zbl 0002.16101)] the authors present a linear time algorithm for finding a Hamiltonian cycle in 4-connected maximal planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q788489$44C02589-6DB9-4932-B130-D40069A0DF61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$5DEB8A8A-9EAE-4C29-BFFA-EB127E042DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$EDC8741C-976B-4E2D-BA40-324B98B4D0CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$FE530D51-9CD4-41E5-AFA8-9373C0823C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$C443F428-2BFF-457D-907A-E29A9E64C7A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8137d324d77ef52c0f6e9d7cef23202b71b39c57","datavalue":{"value":"3843136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$642CA06B-9428-4F30-B584-319C42F71EE8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q788489$2EF0D6FE-0D5D-48A6-9138-1974554139B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q788489$339305FF-F7E9-4449-A652-068319107534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q788489$6FC5AEF2-3AAC-4ACB-862E-4D938989FEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q788489$120CA6BE-DEFE-44AF-84CA-59107C85424A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$A5147ADF-5ABE-4DAA-8121-A1FC52A00008","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":"Q788489$F7A74E70-6D1E-4B5F-B174-82C630E57BB5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$C2EF20C6-F2B3-4717-BABF-3871ACDC4DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$91A18D6A-BA01-4F70-A555-33E68D658AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d52baf2cb84c3f5b903e8477040b67da5cead8f5","datavalue":{"value":{"entity-type":"item","numeric-id":4192099,"id":"Q4192099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$FA454DEB-DAD8-44AB-B779-2318B2EEDB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd492719f080c59c4dd23730fc178cf5a672a45","datavalue":{"value":{"entity-type":"item","numeric-id":1227760,"id":"Q1227760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$863340A3-1E35-4B45-B813-C0069BDC5FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$3CEA85FB-AC81-4BD6-B69E-58ABEA2A459F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba6c020c9b97172623cea215d03785951c408404","datavalue":{"value":{"entity-type":"item","numeric-id":3947135,"id":"Q3947135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$6745B34C-F414-40E2-9FAB-C7ECEBFDBB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$C23CC68C-696F-48AB-B8FC-7543AB7B040E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$76CC1E7F-239E-4011-8306-D3DF39D9A653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788489$A4AD27E2-9712-4F74-A0F6-83C2AAF11C42","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":"Q788489$2E6600D8-39D5-408C-8687-5E8D423E4EE7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3a738d944a6b4b89690fc03a1555bbdbb5ffbd4e","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90109-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q788489$19238E36-28B1-4570-B950-448E9F2B83FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0545ae673abcadf85c4c4a1f0b427927d75dfac7","datavalue":{"value":"W2057568938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788489$D70D25BE-18B5-4258-A446-5CFF5DB788F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c393e8c904fa5682a0d5485e7a97691314983e3a","datavalue":{"value":{"entity-type":"item","numeric-id":3031944,"id":"Q3031944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9dbf974dbe97a2eb5f5e21f6a83c109efda9d03","datavalue":{"value":{"amount":"+0.9231024384498596","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":"Q788489$1D082CA7-2CD5-407A-B4DF-2C7133946943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65cb743cfcced13fc1b94b96179123b8fb66a3d","datavalue":{"value":{"entity-type":"item","numeric-id":2494820,"id":"Q2494820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07af3815124a2d1d36cc0eea5421d1a98a324cdf","datavalue":{"value":{"amount":"+0.8313406705856323","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":"Q788489$24B067B1-C546-4C63-A9B5-A77867789940","rank":"normal"},{"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":"1402c614707fb8e7a315042811799661bc11ca33","datavalue":{"value":{"amount":"+0.8204437494277954","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":"Q788489$6089BC04-7C05-4B0B-A9C4-7F3E93B19A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd9c3b99cf99aab6b790bc274466b0a2d313a990","datavalue":{"value":{"entity-type":"item","numeric-id":2673969,"id":"Q2673969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b514b48bd833d239030d1f038585d57da4b14cc","datavalue":{"value":{"amount":"+0.8096211552619934","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":"Q788489$DFFDEEB5-7E1C-417E-A0F9-5683F0682FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d533ce643728de8c536766f5feced17cba0afe5","datavalue":{"value":{"entity-type":"item","numeric-id":3029036,"id":"Q3029036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ac09eb0e7699f1e72ee9a7c1a5a78a3459d4e30","datavalue":{"value":{"amount":"+0.8072828054428101","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":"Q788489$7EE23D96-7930-4DA8-A4FC-8EDBC0AD27B9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear_algorithm_for_finding_Hamiltonian_cycles_in_4-connected_maximal_planar_graphs"}}}}}