{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T10:51:30Z","timestamp":1676890290729},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p> We introduce a new model of random graphs, that of random regular graphs with edge faults (which we denote by [Formula: see text]), obtained by selecting the edges of a random member of the set of all regular graphs of degree r independently and with probability p. We can thus represent a communication network in which the links fail independently and with probability f =1-p. <\/jats:p><jats:p> In order to deal with this new model, we extend the notion of configurations and the translation lemma between configurations and random regular graphs provided by B. Bollob\u00e1s, by introducing the concept of random configurations, to account for edge faults, and by providing an extended translation lemma between random configurations and [Formula: see text] graphs. <\/jats:p><jats:p> We investigate important connectivity properties of [Formula: see text] by estimating the ranges of r, f for which, with high probability, [Formula: see text] graphs a) are highly connected b) become disconnected and c) admit a giant connected component of small diameter. <\/jats:p>","DOI":"10.1142\/s0129054100000156","type":"journal-article","created":{"date-parts":[[2002,8,24]],"date-time":"2002-08-24T17:40:19Z","timestamp":1030210819000},"page":"247-262","source":"Crossref","is-referenced-by-count":8,"title":["CONNECTIVITY PROPERTIES IN RANDOM REGULAR GRAPHS WITH EDGE FAULTS"],"prefix":"10.1142","volume":"11","author":[{"given":"S.","family":"NIKOLETSEAS","sequence":"first","affiliation":[{"name":"Computer Technology Institute, Patras University, Greece"}]},{"given":"K.","family":"PALEM","sequence":"additional","affiliation":[{"name":"Courant Institute, New York University, USA"}]},{"given":"P.","family":"SPIRAKIS","sequence":"additional","affiliation":[{"name":"Computer Technology Institute, Riga Feraiou Str. 61,  26221 Patras, Greece"}]},{"given":"M.","family":"YUNG","sequence":"additional","affiliation":[{"name":"CertCo NYNY, Columbia University, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110106"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90252-6"},{"key":"p_7","first-page":"47","author":"Bollobas B.","year":"1985","journal-title":"Random Graphs, Annals of Discrete Mathematics"},{"key":"p_10","first-page":"17","volume":"5","author":"Erdos P.","year":"1960","journal-title":"Magyar Tad. Akad. Math. Kut. Int. Kozl."},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"p_15","first-page":"251","author":"Hastad J.","year":"1989","journal-title":"Proceedings of the 21st ACM Symposium on Theory of Computing (STOC)"},{"key":"p_16","first-page":"232","volume":"4","author":"Janson S.","year":"1993","journal-title":"Journal of Random Structures and Algorithms"},{"key":"p_18","first-page":"138","author":"Kedem Z.","year":"1990","journal-title":"Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC)"},{"key":"p_23","first-page":"508","author":"Nikoletseas S.","year":"1994","journal-title":"21st International Colloquium on Automata, Jerusalem"},{"key":"p_25","first-page":"208","author":"Nikoletseas S.","year":"1997","journal-title":"3rd International European Conference on Parallel Processing (Euro-Par)"},{"key":"p_26","first-page":"421","author":"Nikoletseas S.","year":"1995","journal-title":"12th Annual Symposium on Theoretical Aspects of Computer Science (STAGS), Munchen"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62050"},{"key":"p_29","first-page":"436","volume":"48","author":"Turan P.","year":"1941","journal-title":"Matematicko Fizicki Lapok"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80022-6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:33:51Z","timestamp":1565177631000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":15,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,6]]}},"alternative-id":["10.1142\/S0129054100000156"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000156","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}