{"entities":{"Q3031944":{"pageid":3042660,"ns":120,"title":"Item:Q3031944","lastrevid":45302878,"modified":"2025-12-04T13:55:29Z","type":"item","id":"Q3031944","labels":{"en":{"language":"en","value":"The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130041"}},"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":"Q3031944$15A7166B-2AAA-4AB3-BE9D-AFD6D7E9D069","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"219ab2fe08e25e997eb004a00b80a9b2dc2372c6","datavalue":{"value":{"text":"The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3031944$335D5134-DBDC-4C74-8649-7EBC14BAA5BD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"387d92a6c986b32df0a1d11bbc7f33a3f8cabb4d","datavalue":{"value":"0689.68089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$D6CF964E-2E12-4A5D-9697-0A7E3DEBEC0E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b25d6797ad0ac0003cad3fdf91a7db755b30321","datavalue":{"value":"10.1016/0196-6774(89)90012-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$D1C1F6ED-E7BE-473B-9EEB-01A68ED0EFE0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ee68de2af4277a285837f24c0d6ec9f5b26f572","datavalue":{"value":{"entity-type":"item","numeric-id":205117,"id":"Q205117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3031944$71652659-966D-4BBC-8CFC-B243C5BF3DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da93d7c45d552338138e673e141df03679ac5cb5","datavalue":{"value":{"entity-type":"item","numeric-id":226821,"id":"Q226821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3031944$0D4D05BA-9D4E-4BF6-914A-B1F32E2B9954","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3031944$F507F66F-10E1-41F5-B2BC-0BC2F0B51ED9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q3031944$93DF32AB-4DE5-4F33-AA8E-3E1AB2AC5ED1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$4522ABDA-C159-4BB1-BF8D-1553644F5352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$4E4EF7C1-39FA-4218-B7E1-38C3818141D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$A0B22129-D084-4336-AA60-2F42649A9542","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd31ced90de6c08c4f33687e7b08f4e14f1677e0","datavalue":{"value":"4130041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$BDAC445B-C29A-4CF2-A7A2-0C3BDF926383","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35f6e12279431f0167e4b6d99fb9654e2fb19b1f","datavalue":{"value":"Hamiltonian cycle problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3031944$BFF4BE82-9C9B-4833-AD92-4BF961EC5478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3031944$D9845716-F900-4D4E-82B1-254CF9AC7AE6","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":"Q3031944$9ED6D41D-B9EE-45D7-9A68-D10FEF547729","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9dc1f6e0b73bc1dc6f42fb8553a483c3354ee2d","datavalue":{"value":"https://doi.org/10.1016/0196-6774(89)90012-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q3031944$DAB8C94B-862D-440D-A7FC-00B1D140495F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e02350ba28fca6701572dc7812d73f97e9dc20c","datavalue":{"value":"W1983755786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$0AF31C2A-B41F-4FE6-8F82-E1D82B373520","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"94af2171a834abc4c9d739de602b8ec7fe7f4c90","datavalue":{"value":"Q56138404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3031944$564CC899-1C7C-4917-858E-EBDD127AE7F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a73e8468889f69015b58b2892978271685a91721","datavalue":{"value":{"entity-type":"item","numeric-id":788489,"id":"Q788489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073a82a383bc8ac5d270c907036f532eee27a51c","datavalue":{"value":{"amount":"+0.91914076","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":"Q3031944$4D9DA609-B7A1-41EE-B1DA-56FDA67C7EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1152287fdd36912824346b90ed2c2fa062b5f1e","datavalue":{"value":{"entity-type":"item","numeric-id":968420,"id":"Q968420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3105796c473cd8d7a9f1ddf0ece2cc87f0f49bb","datavalue":{"value":{"amount":"+0.88368016","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":"Q3031944$EAED8F86-2F96-4BD3-92EB-F8E92D4DA714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b8f518ec8b284c96ff310b669cb72ef61efac1","datavalue":{"value":{"entity-type":"item","numeric-id":1340124,"id":"Q1340124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26c7bce5f6337d3116e0f219b8178f107c2983cf","datavalue":{"value":{"amount":"+0.8827999","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":"Q3031944$AB57CA11-C915-4BFA-9AA8-B1D0B65BD0C0","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":"78b94a4a25a382d60bd494c0362caa95617cefae","datavalue":{"value":{"amount":"+0.87972975","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":"Q3031944$A84ED2F6-A59D-4506-B0CD-2C3CD732F1B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb07382b79d0a1d5d39f15084d8a5ce9c8ed17d8","datavalue":{"value":{"entity-type":"item","numeric-id":5193693,"id":"Q5193693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"428ab60b1ec6b02a2bdf9746a52c8453698a1ff0","datavalue":{"value":{"amount":"+0.87832487","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":"Q3031944$38C31769-6FCD-470F-854A-C25C6E2DF584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69faf95caf62ce459219fcdeb2e45953665d8a36","datavalue":{"value":{"entity-type":"item","numeric-id":4607996,"id":"Q4607996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65108197aabd512c49495df8755ad00d2cbbe693","datavalue":{"value":{"amount":"+0.8741062","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":"Q3031944$D6AEE95A-9D7C-44E7-A75F-C3E3CCA9896E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9a616ff836fd19d68d24817e65050a1e8416024","datavalue":{"value":{"entity-type":"item","numeric-id":2005718,"id":"Q2005718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49ca6e8bb10e5cab4ad018b6a4fdc8ff49532068","datavalue":{"value":{"amount":"+0.8680041","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":"Q3031944$C338D8AA-DD09-4D7F-886D-CEB51A4F655F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c15f6bae4a8bc5e94583b579f0005ee8dde3106b","datavalue":{"value":{"entity-type":"item","numeric-id":442328,"id":"Q442328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"507cd2edfafca405215154e9abed456b5e26f73d","datavalue":{"value":{"amount":"+0.8634409","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":"Q3031944$EFCC3312-282B-43B9-B18B-0266D6A6D69E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cabbc188614dcd8bcb3a26fa875814604282d4b","datavalue":{"value":{"entity-type":"item","numeric-id":4265590,"id":"Q4265590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a079988eaf30454a1ab1a7c555510384bde4ba3c","datavalue":{"value":{"amount":"+0.86288637","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":"Q3031944$0B5FB7F8-174A-4154-B3EF-8DF0B261649E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee85e5dd89c1a2c13f5fb61415d5238d86681769","datavalue":{"value":{"entity-type":"item","numeric-id":726634,"id":"Q726634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"762b41710dd68fa5df7c3c1821a7f65799005505","datavalue":{"value":{"amount":"+0.8622712","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":"Q3031944$4D1F70F3-DE16-4F44-A428-80DFBA2B0452","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3031944","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3031944"}}}}}