{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T18:09:39Z","timestamp":1698516579842},"reference-count":18,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4485,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider a random graph <jats:italic>G<\/jats:italic> composed of a Hamiltonian cycle on <jats:italic>n<\/jats:italic> labeled vertices and <jats:italic>dn<\/jats:italic> random edges that \u201chigh\u201d the cycle. Is it possible to unravel the structures, that is, to efficiently find a Himiltonian cycle in <jats:italic>G<\/jats:italic>? We describe an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup> log <jats:italic>n<\/jats:italic>)\u2010step algorithm <jats:italic>A<\/jats:italic> for this purpose, and prove that it succeeds almost surely. Part one of <jats:italic>A<\/jats:italic> properly covers the \u201ctrouble spots\u201d of <jats:italic>G<\/jats:italic> by a collection of disjoint paths. (This is the hard part to analyze). Part two of <jats:italic>A<\/jats:italic> extends this cover to a full cycle by the rotation\u2010extension technique which is already classical for such problems. \u00a9 1994 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050303","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T20:17:58Z","timestamp":1180729078000},"page":"395-410","source":"Crossref","is-referenced-by-count":9,"title":["Finding hidden hamiltonian cycles"],"prefix":"10.1002","volume":"5","author":[{"given":"Andrei Z.","family":"Broder","sequence":"first","affiliation":[]},{"given":"Alan M.","family":"Frieze","sequence":"additional","affiliation":[]},{"given":"Eli","family":"Shamir","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"e_1_2_1_3_2","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579321"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"A. Z.Broder A. M.Frieze andE.Shamir Finding hidden Hamiltonian cycles Proc. 23rd Annual ACM Symposium on Theory of Computing May1991 pp.182\u2013189.","DOI":"10.1145\/103418.103442"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"R.Boppana Eigenvalues and graph bisection: an average\u2010case analysis Proc. 28th Annual Symposium on Foundations of Computer Science October1987 pp.280\u2013285.","DOI":"10.1109\/SFCS.1987.22"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579448"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90001-1"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90046-8"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216068"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90089-5"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216034"},{"key":"e_1_2_1_13_2","unstructured":"L.Kuccaron;eraandS.Micali Cryuptography and random graphs unpublished manuscript 1988."},{"key":"e_1_2_1_14_2","unstructured":"M. R.Jerrum private communication 1992."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030202"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579348"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215041"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:37:22Z","timestamp":1698205042000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,7]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,7]]}},"alternative-id":["10.1002\/rsa.3240050303"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050303","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,7]]}}}