{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:52:47Z","timestamp":1740099167455,"version":"3.37.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030013240"},{"type":"electronic","value":"9783030013257"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-01325-7_11","type":"book-chapter","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T17:43:05Z","timestamp":1540921385000},"page":"72-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in $$O(\\log n)$$ Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9964-8816","authenticated-orcid":false,"given":"Volker","family":"Turau","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,31]]},"reference":[{"issue":"2","key":"11_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D Angluin","year":"1979","unstructured":"Angluin, D., Valiant, L.: Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci. 18(2), 155\u2013193 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"11_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.2307\/1998567","volume":"267","author":"B Bollob\u00e1s","year":"1981","unstructured":"Bollob\u00e1s, B.: The diameter of random graphs. Trans. Am. Math. Soc. 267(1), 41\u201352 (1981)","journal-title":"Trans. Am. Math. Soc."},{"key":"11_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02579321","volume":"7","author":"B Bollob\u00e1s","year":"1987","unstructured":"Bollob\u00e1s, B., Fenner, T.I., Frieze, A.M.: An algorithm for finding hamilton paths and cycles in random graphs. Combinatorica 7(4), 327\u2013341 (1987)","journal-title":"Combinatorica"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Fathi, R., Pandurangan, G., Dinh Pham, N.: Fast and efficient distributed computation of Hamiltonian cycles in random graphs. In: 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018, Vienna, Austria, 2\u20136 July 2018, pp. 764\u2013774 (2018). https:\/\/doi.org\/10.1109\/ICDCS.2018.00079","DOI":"10.1109\/ICDCS.2018.00079"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/aama.2001.0720","volume":"26","author":"F Chung","year":"2001","unstructured":"Chung, F., Lu, L.: The diameter of sparse random graphs. Adv. Appl. Math. 26(4), 257\u2013279 (2001)","journal-title":"Adv. Appl. Math."},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs I. Publ. Math. (Debr.) 6, 290\u2013297 (1959)","journal-title":"Publ. Math. (Debr.)"},{"issue":"11","key":"11_CR8","doi-asserted-by":"publisher","first-page":"2495","DOI":"10.1016\/j.automatica.2011.08.032","volume":"47","author":"M Franceschelli","year":"2011","unstructured":"Franceschelli, M., Giua, A., Seatzu, C.: Quantized consensus in hamiltonian graphs. Automatica 47(11), 2495\u20132503 (2011)","journal-title":"Automatica"},{"issue":"2","key":"11_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(87)90229-8","volume":"25","author":"A Frieze","year":"1987","unstructured":"Frieze, A.: Parallel algorithms for finding hamilton cycles in random graphs. Inf. Process. Lett. 25(2), 111\u2013117 (1987)","journal-title":"Inf. Process. Lett."},{"key":"11_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to Random Graphs","author":"A Frieze","year":"2015","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2015)"},{"issue":"1","key":"11_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.20542","volume":"47","author":"AM Frieze","year":"2015","unstructured":"Frieze, A.M., Haber, S.: An almost linear time algorithm for finding hamilton cycles in sparse random graphs with minimum degree at least three. Random Struct. Algorithms 47(1), 73\u201398 (2015)","journal-title":"Random Struct. Algorithms"},{"key":"11_CR12","unstructured":"H\u00e9lary, J., Raynal, M.: Depth-first traversal and virtual ring construction in distributed systems. Research Report RR-0704, INRIA Rennes (1987)"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Kim, J., Srikant, R.: Peer-to-peer streaming over dynamic random hamilton cycles. In: 2012 Infernational Theory & Applications Workshop, pp. 415\u2013419, February 2012","DOI":"10.1109\/ITA.2012.6181767"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0012-365X(83)90021-3","volume":"43","author":"J Koml\u00f3s","year":"1983","unstructured":"Koml\u00f3s, J., Szemer\u00e9di, E.: Limit distribution for the existence of hamiltonian cycles in a random graph. Discret. Math. 43(1), 55\u201363 (1983)","journal-title":"Discret. Math."},{"key":"11_CR15","series-title":"London Mathematical Society Student Texts (84)","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316479988","volume-title":"Random Graphs, Geometry and Asymptotic Structure\u2018","author":"M Krivelevich","year":"2016","unstructured":"Krivelevich, M., Panagiotou, K., Penrose, M., McDiarmid, C.: Random Graphs, Geometry and Asymptotic Structure\u2018. London Mathematical Society Student Texts (84). Cambridge University Press, Cambridge (2016)"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2015.08.037","volume":"605","author":"K Krzywdzi\u0144ski","year":"2015","unstructured":"Krzywdzi\u0144ski, K., Rybarczyk, K.: Distributed algorithms for random graphs. Theor. Comput. Sci. 605, 95\u2013105 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/11527954_7","volume-title":"Combinatorial and Algorithmic Aspects of Networking","author":"E Levy","year":"2005","unstructured":"Levy, E., Louchard, G., Petit, J.: A distributed algorithm to find hamiltonian cycles in $$\\cal{G}(n, p)$$ random graphs. In: L\u00f3pez-Ortiz, A., Hamel, A.M. (eds.) CAAN 2004. LNCS, vol. 3405, pp. 63\u201374. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11527954_7"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"MacKenzie, P.D., Stout, Q. F.: Optimal parallel construction of hamiltonian cycles and spanning trees in random graphs. In: Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms & Architectures, pp. 224\u2013229, New York (1993)","DOI":"10.1145\/165231.165260"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-04355-0_42","volume-title":"Distributed Computing","author":"D Malkhi","year":"2009","unstructured":"Malkhi, D., Sen, S., Talwar, K., Werneck, R.F., Wieder, U.: Virtual ring routing trends. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 392\u2013406. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04355-0_42"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. In: Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"4","key":"11_CR21","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L P\u00f3sa","year":"1976","unstructured":"P\u00f3sa, L.: Hamiltonian circuits in random graphs. Discret. Math. 14(4), 359\u2013364 (1976)","journal-title":"Discret. Math."},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02579348","volume":"3","author":"E Shamir","year":"1983","unstructured":"Shamir, E.: How many random edges make a graph hamiltonian? Combinatorica 3(1), 123\u2013131 (1983)","journal-title":"Combinatorica"},{"issue":"1","key":"11_CR23","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/0012-365X(89)90100-3","volume":"75","author":"A Thomason","year":"1989","unstructured":"Thomason, A.: A simple linear expected time algorithm for finding a hamilton path. Discret. Math. 75(1), 373\u2013379 (1989)","journal-title":"Discret. Math."},{"key":"11_CR24","unstructured":"Turau, V.: A Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in $$O(\\log n)$$ Time. (2018). arXiv preprint arXiv:1805.06728"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Turau, V., Siegemund, G.: Scalable routing for topic-based publish\/subscribe systems under fluctuations. In: Proceedings of the 37th International Conference on Distributed Computing Systems (2017)","DOI":"10.1109\/ICDCS.2017.27"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-01325-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T15:30:48Z","timestamp":1694014248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-01325-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030013240","9783030013257"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-01325-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ma'ale HaHamisha","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/sirocco2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"47","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"49% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"1.97","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}