{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:35Z","timestamp":1725467915643},"publisher-location":"Berlin\/Heidelberg","reference-count":21,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040407","type":"book-chapter","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T20:03:50Z","timestamp":1154549030000},"page":"401-410","source":"Crossref","is-referenced-by-count":4,"title":["The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels"],"prefix":"10.1007","author":[{"given":"Charles U.","family":"Martel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas P.","family":"Vayda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","unstructured":"Abrahamson, K., Personal Communication, Department of Computer Science, Washington State University, September, 1987."},{"issue":"5","key":"40_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","volume":"OT-25","author":"J. I. Capetanakis","year":"1979","unstructured":"Capetanakis, J. I., Tree Algorithms for Packet Broadcast Channels, IEEE Transactions on Information Theory, Vol. OT-25, No. 5, (September 1979) pp. 505\u2013515.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"40_CR3","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/TC.1986.1676745","volume":"C-35","author":"R. Dechter","year":"1986","unstructured":"Dechter, R. and Kleinrock, L., Broadcast Communications and Distributed Algorithms. IEEE Transactions on Computers, Vol. C-35, No. 3, (March 1986) pp. 210\u2013219.","journal-title":"IEEE Transactions on Computers"},{"key":"40_CR4","unstructured":"Fich, F.E., Ragde, P.L., and Wigderson, A., Relations Between Concurrent-Write Models of Parallel Computation, To appear in SIAM Journal on Computing."},{"key":"40_CR5","unstructured":"Greenberg, A., On the Time Complexity of Broadcast Communication Schemes. Proceedings of the 14th Symposium on the Theory of Computing, (1984) pp. 354\u2013364."},{"key":"40_CR6","series-title":"T.R. No.","volume-title":"Efficient Algorithms for Multiple Access Channels","author":"A. G. Greenberg","year":"1983","unstructured":"Greenberg, A. G., Efficient Algorithms for Multiple Access Channels, T.R. No. #83-08-01 Department of Computer Science, University of Washington, Seattle, August 1983."},{"issue":"2","key":"40_CR7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/23005.23006","volume":"34","author":"A. G. Greenberg","year":"1987","unstructured":"Greenberg, A. G., Flajolet, P. and Ladner, R. E., Estimating the Multiplicities of Conflicts to Speed Their Resolution in Multiple Access Channels, Journal of the Association for Computing Machinery, Vol. 34, No. 2, (April 1987) pp. 289\u2013325.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Greenberg, A. G., Lubachevsky, B. D. and Odlyzko, A. M., Simple, Efficient Asynchronous Parallel Algorithms for Maximization. Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, (August 1985) pp. 300\u2013308.","DOI":"10.1145\/323596.323625"},{"issue":"3","key":"40_CR9","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1145\/3828.214125","volume":"32","author":"A. Greenberg","year":"1985","unstructured":"Greenberg, A. and Winograd, S., A lower bound on time needed in the worst case to resolve conflicts deterministically in multiple access channels. Journal of the ACM, Vol. 32, No. 3, (July 1985) pp. 589\u2013596.","journal-title":"Journal of the ACM"},{"issue":"8","key":"40_CR10","doi-asserted-by":"publisher","first-page":"1178","DOI":"10.1109\/TCOM.1978.1094204","volume":"COM-26","author":"J. F. Hayes","year":"1978","unstructured":"Hayes, J. F., An Adaptive Technique for Local Distribution. IEEE Transactions on Communications, Vol. COM-26, No. 8, (August 1978) pp. 1178\u20131186.","journal-title":"IEEE Transactions on Communications"},{"key":"40_CR11","unstructured":"IEEE Project 802, Draft IEEE Standard 802.3 CSMA\/CD Access Method and Physical Layer Specifications. IEEE Computer Society, Revision D, December 1982"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Komlos, J. and Greenberg, A. G. An Asymptotically Fast Non-adaptive Algorithm for Conflict Resolution in Multiple Access Channels, IEEE Trans. Inf. Theory (March 1985)","DOI":"10.1109\/TIT.1985.1057020"},{"key":"40_CR13","unstructured":"Levitan, S., Algorithms for Broadcast Protocol Multiprocessors. Proceedings of the 3rd International Conference on Distributed Computer Systems, (1982) pp. 666\u2013671."},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Levitan, S. P. and Foster, C., Finding an Extremum in a Network. Proceedings Ninth International Symposium of Computer Architecture, (April 1982) pp. 321\u2013325.","DOI":"10.1145\/1067649.801741"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Martel, C., Gusfield, D. A Fast Parallel Quicksort Algorithm, Preprint, U.C. Davis, 1988","DOI":"10.1016\/0020-0190(89)90116-6"},{"key":"40_CR16","unstructured":"Martel, C. and Vayda, T. Load Estimation, Problem Size Reduction and Maximum Finding in Multiple Access Broadcast Networks. Proc. of 25th Annual Allerton Conf., Oct. 1987."},{"issue":"7","key":"40_CR17","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/360248.360253","volume":"19","author":"R. Metcalfe","year":"1976","unstructured":"Metcalfe, R. and Boggs, D., Ethernet: Distributed Packet Switching for Local Computer Networks. Communications of the ACM, Vol. 19, No. 7, (July 1976) pp. 395\u2013404.","journal-title":"Communications of the ACM"},{"key":"40_CR18","unstructured":"Ragde, P. Lower Bounds for Parallel Computation, Ph.D. Thesis, U.C. Berkeley 1986."},{"key":"40_CR19","volume-title":"On the Complexity of Parallel Algorithms for Multiple Access Networks","author":"T. P. Vayda","year":"1988","unstructured":"Vayda, T. P., On the Complexity of Parallel Algorithms for Multiple Access Networks, Ph.D. Thesis, Division of Computer Science, U.C. Davis, Davis Ca. 1988."},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Wah, B. and Juang, J., Resource Scheduling for Local Computer Systems with a Multiaccess Network. IEEE Transactions on Computers, Vol. C-34, No. 12, (December 1985)","DOI":"10.1109\/TC.1985.6312212"},{"issue":"2","key":"40_CR21","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1137\/0215032","volume":"15","author":"D. E. Willard","year":"1986","unstructured":"Willard, D. E., Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel. SIAM Journal of Computing, Vol. 15, No. 2, (May 1986) pp. 468\u2013477.","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040407.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T07:34:21Z","timestamp":1683531261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/bfb0040407","relation":{},"subject":[]}}