{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:49:48Z","timestamp":1725490188783},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_32","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:17:32Z","timestamp":1188335852000},"page":"374-385","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic Broadcasting Time with Partial Knowledge of the Network"],"prefix":"10.1007","author":[{"given":"Gianluca","family":"De Marco","sequence":"first","affiliation":[]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"S. Albers and M. R. Henzinger, Exploring unknown environments, Proc. 29th Symp. on Theory of Computing (1997), 416\u2013425.","DOI":"10.1145\/258533.258630"},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0020-0190(85)90083-3","volume":"20","author":"B. Awerbuch","year":"1985","unstructured":"B. Awerbuch, A new distributed depth-first-search algorithm, Information Processing Letters 20 (1985), 147\u2013150.","journal-title":"Information Processing Letters"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1145\/77600.77618","volume":"37","author":"B. Awerbuch","year":"1990","unstructured":"B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A Tradeoff Between Information and Communication in Broadcast Protocols, J. ACM 37, (1990), 238\u2013256.","journal-title":"J. ACM"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization, Proc. 6th ACM Symp. on Principles of Distr. Comp. (1987), 98\u2013108.","DOI":"10.1145\/41840.41849"},{"key":"32_CR5","unstructured":"B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc and W. Rytter, Deterministic broadcasting in unknown radio networks, Proc. 11th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA\u20192000), 861\u2013870."},{"key":"32_CR6","unstructured":"G. De Marco and A. Pelc, Fast distributed graph coloring with O(\u0394) colors, manuscript."},{"key":"32_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-48481-7_5","volume-title":"The impact of knowledge on broadcasting time in radio networks","author":"K. Diks","year":"1999","unstructured":"K. Diks, E. Kranakis, D. Krizanc and A. Pelc, The impact of knowledge on broadcasting time in radio networks, Proc. 7th Annual European Symposium on Algorithms, ESA\u201999, Prague, Czech Republic, July 1999, LNCS 1643, 41\u201352."},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"D. Z. Du and F. H. Hwang, Combinatorial group testing and its applications, World Scientific, Singapore, 1993.","DOI":"10.1142\/1936"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"S. Even and B. Monien, On the number of rounds necessary to disseminate information, Proc. 1st ACM Symp. on Par. Alg. and Arch., June 1989, 318\u2013327.","DOI":"10.1145\/72935.72969"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1002\/rsa.3240010406","volume":"1","author":"U. Feige","year":"1990","unstructured":"U. Feige, D. Peleg, P. Raghavan and E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (1990), 447\u2013460.","journal-title":"Random Structures and Algorithms"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P. Fraigniaud","year":"1994","unstructured":"P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Disc. Appl. Math. 53 (1994), 79\u2013133.","journal-title":"Disc. Appl. Math."},{"key":"32_CR12","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, A. Pelc, D. Peleg and S. Perennes, Assigning labels in unknown anonymous networks, Proc. 19th ACM Symp. on Principles of Distributed Computing (PODC\u20192000), July 2000, Portland, Oregon, U.S.A., 101\u2013112.","DOI":"10.1145\/343477.343527"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"L. Gargano, A. Pelc, S. Perennes and U. Vaccaro, Efficient communication in unknown networks, Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u20192000), June 2000, Konstanz, Germany, to appear.","DOI":"10.1007\/3-540-40064-8_17"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1006\/jpdc.1997.1303","volume":"42","author":"L. Gasieniec","year":"1997","unstructured":"L. Gasieniec and A. Pelc, Broadcasting with a bounded fraction of faulty nodes, Journal of Parallel and Distributed Computing 42 (1997), 11\u201320.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S.M. Hedetniemi","year":"1988","unstructured":"S.M. Hedetniemi, S.T. Hedetniemi and A.L. Liestman, A survey of Gossiping and Broadcasting in Communication Networks, Networks 18 (1988), 319\u2013349.","journal-title":"Networks"},{"issue":"2","key":"32_CR16","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TIT.1985.1057020","volume":"IT-31","author":"J. Koml\u00f3s","year":"1985","unstructured":"J. Koml\u00f3s and A. G. Greenberg, An asymptotically nonadaptive algorithm for con ict resolution in multiple-access channels, IEEE Trans. on Information Theory, IT-31 n. 2 (1985), 302\u2013306.","journal-title":"IEEE Trans. on Information Theory"},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1137\/0221026","volume":"21","author":"D.W. Krumme","year":"1992","unstructured":"D.W. Krumme, Fast gossiping for the hypercube, SIAM J. Computing 21 (1992), 365\u2013380.","journal-title":"SIAM J. Computing"},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"N. Linial, Locality in distributed graph algorithms, SIAM J. Computing 21 (1992), 193\u2013201.","journal-title":"SIAM J. Computing"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"P. Panaite and A. Pelc, Exploring unknown undirected graphs, Proc. 9th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998), 316\u2013322.","DOI":"10.1006\/jagm.1999.1043"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:25:52Z","timestamp":1556803552000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}