{"entities":{"Q1080865":{"pageid":1091617,"ns":120,"title":"Item:Q1080865","lastrevid":66850683,"modified":"2026-04-12T13:16:47Z","type":"item","id":"Q1080865","labels":{"en":{"language":"en","value":"Finding Hamilton cycles in sparse random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3968619"}},"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":"Q1080865$AD956E5C-E3A7-447C-AFDF-E67516AE2A19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2e0777ccfc352b8cb35eb3141dd9b2c3fea33d4","datavalue":{"value":{"text":"Finding Hamilton cycles in sparse random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1080865$79A71D70-80D6-4259-9F4B-9EF4DA050608","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"282a3aa3c242d70c9141b0136be801dbf5d72b30","datavalue":{"value":"0601.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$5880420F-81AF-4561-A494-27015B36B634","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a684c5ab3791d372e740969962f2df970477232","datavalue":{"value":"10.1016/0095-8956(88)90089-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$5154B65D-BC12-4176-8D0D-2674D20ED8E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$78C1D0FA-1162-4B2C-B45D-8793898E22AE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1080865$D03EB962-1EBC-4455-9685-FCE7CD59C220","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a85f823407da2958f1bcbc7fd82918791d9d76fe","datavalue":{"value":"We describe a polynomial time \\((O(n^ 3\\log n))\\) algorithm which has a high probability of finding Hamilton cycles in 2 classes of random graph which have constant average degree: the m-out model and the random regular graph model. We also show how the algorithm can be used to find a large cycle in a sparse random graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080865$62AA4D93-7163-4C10-BEAB-33C96F377A51","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$B1F4D6E7-7CBA-47E4-A8C1-8C78C30ACCA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$245DB5E3-5D81-4914-B68B-0BF0C3DE7B8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$52AF5E9F-466D-4DAC-9C15-50ADA475058E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2aa986001e312056b8ccb1c650ac22da7d05956","datavalue":{"value":"3968619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$8B0050C3-6313-4A65-81BC-8A0FE21BA9C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080865$3765EE55-2AD1-4773-ABAF-80CD1B35855C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c51a5f2b554ad725199c724ddbac3b61a9fd8af1","datavalue":{"value":"Hamilton cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080865$0C8F931C-A643-45F4-B12F-AFE0A63303A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1080865$A0D623D2-29A9-406C-94F2-4E4025711CD4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6062ca6683640dddc4df09249c9f2eab5866999c","datavalue":{"value":"Q57401615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$1F80F0AF-70A6-412D-B40D-A28DB1653389","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$D722817E-B79A-43B5-A552-00E9F0964CA6","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":"Q1080865$37AD0FD0-005B-42A7-8B6E-A8B3E1E646AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea4c1559c7e3dcf51f6f64d95a6da691a7fbca26","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90089-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1080865$F7D74703-D79E-4FD0-B192-2DC46097F012","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"745d837c28e5f91859608b9a074df0ce4e39c950","datavalue":{"value":"W2017777628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1080865$5DE3394B-1AA1-4C82-BEFC-E1ECBFBF85F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22c9192954ccc96b2ee3267d39b3b42b3eff67b4","datavalue":{"value":{"entity-type":"item","numeric-id":1166543,"id":"Q1166543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$5694FF41-F446-496E-B464-67EC48E14CEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$4F5E41FB-1996-4AE3-ADFA-E6F6AA579B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34fb167d6b58149e4c07bc6f477f173f3d07b81","datavalue":{"value":{"entity-type":"item","numeric-id":1150630,"id":"Q1150630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$4320CC11-38DF-46C2-AEA7-91FE08BAD991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d035933938e805a75565dd399f688395cd7d72","datavalue":{"value":{"entity-type":"item","numeric-id":594110,"id":"Q594110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$4A51D7E0-2090-4682-ABC2-D6EB1CD20C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a55c3a24960786fcf08168b321bfcd461ac080a","datavalue":{"value":{"entity-type":"item","numeric-id":1050368,"id":"Q1050368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$DE879F32-F0F1-467E-B2F4-8BBC5203AF55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f3e6a00720528a1dcbef8f2404f730f0310dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4487074,"id":"Q4487074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$23C2A6CC-50F4-4C0B-A078-1132055AD7A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48f21625b4cd924340c3b2deef95d9d355d316cb","datavalue":{"value":{"entity-type":"item","numeric-id":1056764,"id":"Q1056764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$FD11F32D-8A4A-4B99-BB3D-B5A84E04FB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18ee6d84c5e14ca6122a1c73bc9a73a2603962a3","datavalue":{"value":{"entity-type":"item","numeric-id":1838982,"id":"Q1838982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$FD7F0A0B-D6C2-4174-9963-5A7C8E52D08F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c50119c64934cf7e7374575d286b63bde25ee55","datavalue":{"value":{"entity-type":"item","numeric-id":1063002,"id":"Q1063002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$95A168B6-F7D5-4E6B-BFEC-53E6CD27F1BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eeff2192304a70455454c7d5bd957bf9891a8e2","datavalue":{"value":{"entity-type":"item","numeric-id":3887496,"id":"Q3887496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$90B5A093-2B88-4C1A-BFBE-755F4C40E085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5df85ee70a104904416be57c740c463f19ac9791","datavalue":{"value":{"entity-type":"item","numeric-id":1092926,"id":"Q1092926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$B8293100-85C2-43AE-9B0C-90CBE0239AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0605ce8023dcad6d8b397528b4dd00d8f78600e6","datavalue":{"value":{"entity-type":"item","numeric-id":3801370,"id":"Q3801370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$5263A079-D295-4DAA-8E78-5FA04F58565F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$0D293CC7-F023-4E4D-9DEE-6D7573C689A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e11bf65cb6459492b00543657811c7c16e1dde47","datavalue":{"value":{"entity-type":"item","numeric-id":1055441,"id":"Q1055441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$DC6A0B36-FE35-4A0D-B074-B50A3EE8398A","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":"Q1080865$AB0CB171-5BC7-4171-8409-F2BD393CF89E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7cfd63ad734715aefaa5d61e6921045c1afbef","datavalue":{"value":{"entity-type":"item","numeric-id":1055442,"id":"Q1055442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1080865$B84423DB-F479-4C6E-A794-BC2E458AFD61","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92a37aa3a7f3c715ce5b947fa300dd2a4b5093f9","datavalue":{"value":{"entity-type":"item","numeric-id":3192373,"id":"Q3192373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a7d4b640f6c455e5fbd6c5c89154cf8f1cd1278","datavalue":{"value":{"amount":"+0.92671000957489","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":"Q1080865$EE985575-167C-41B2-B87E-974AB211CE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7b63c87a4908c06903cef75e58e5ed0d5f970a2","datavalue":{"value":{"entity-type":"item","numeric-id":1041775,"id":"Q1041775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8046e0005d43aef96b13513f168219b88e21388f","datavalue":{"value":{"amount":"+0.9253062605857848","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":"Q1080865$5EB8053F-D8BF-4382-BFE4-8C89B222B265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5fe922d0399afad5bc5846ecd4ff75e02baae2","datavalue":{"value":{"entity-type":"item","numeric-id":5300478,"id":"Q5300478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f15c6962fef441fff4e66c2d7ad8fcd6bc4b00b6","datavalue":{"value":{"amount":"+0.9212930202484132","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":"Q1080865$65E0B08B-D334-4D19-AE8D-312DD2726067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9d5d984f4212c6599af63b781a1645abe7eb41","datavalue":{"value":{"entity-type":"item","numeric-id":3790664,"id":"Q3790664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8e67d217c7b442e395c5decf2f275108119d04b","datavalue":{"value":{"amount":"+0.888170599937439","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":"Q1080865$59B86D90-64F0-43E5-AF5D-70D2A36A0DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ee60615e9604043b25cd52b722cff3e92cb917","datavalue":{"value":{"entity-type":"item","numeric-id":4306372,"id":"Q4306372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8b467f77067f552d91d04efdc6233698025ef0b","datavalue":{"value":{"amount":"+0.8812255263328552","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":"Q1080865$3E5CC9D5-05F1-4FF2-923B-262B31EBF1D9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding Hamilton cycles in sparse random graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_Hamilton_cycles_in_sparse_random_graphs"}}}}}