{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:41Z","timestamp":1773704801801,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf01303516","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T08:01:50Z","timestamp":1111737710000},"page":"441-454","source":"Crossref","is-referenced-by-count":143,"title":["Low diameter graph decompositions"],"prefix":"10.1007","volume":"13","author":[{"given":"Nathan","family":"Linial","sequence":"first","affiliation":[]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Y. Afek andM. Ricklin: Sparser: A paradigm for running distributed algorithms, 6th International Workshop, on Distributed Algorithms, Haifa, Israel November 1992, Springer-Verlag. (J. of Algorithms, in press).","DOI":"10.1007\/3-540-56188-9_1"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, andA. Itai: A fast and simple randomized parallel algorithm for the maximal independent set problem,J. of Algorithms 7 (1986), 567?583.","journal-title":"J. of Algorithms"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"B. Awerbuch: Complexity of network synchronization,J. ACM 32 (1985), 804?823.","journal-title":"J. ACM"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Goldberg. M. Luby, andS. Plotkin: Network decomposition and locality in distributed computation,Proc. 30th IEEE Symp. on Foundations of Comp. Sci. (1989) 364?369.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"CR5","first-page":"503","volume":"31","author":"B. Awerbuch","year":"1990","unstructured":"B. Awerbuch andD. Peleg: Sparse partitions,FOCS 31 (1990), 503?513.","journal-title":"FOCS"},{"key":"CR6","volume-title":"An Introduction to Algebraic and Combinatorial Coding Theory","author":"I. F. Blake","year":"1976","unstructured":"I. F. Blake andR. C. Mullin:An Introduction to Algebraic and Combinatorial Coding Theory, Academic Press, New York, 1976."},{"key":"CR7","volume-title":"Extremal graph theory","author":"B. Bollob\ufffds","year":"1987","unstructured":"B. Bollob\ufffds:Extremal graph theory, Academic Press, New York, 1987."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"R. Cole andU. Vishkin: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms,Proc. 18th ACM Sump. on Theory of Computing (1986) 206?219.","DOI":"10.1145\/12130.12151"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0097-3165(81)90027-3","volume":"30","author":"R. M. Freund","year":"1981","unstructured":"R. M. Freund andM. J. Todd: A constructive proof of Tucker's combinatorial lemma.J. Comb. Theory A 30 (1981) 321?325.","journal-title":"J. Comb. Theory A"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1080\/00029890.1979.11994922","volume":"86","author":"D. Gale","year":"1979","unstructured":"D. Gale: The game of hex and the Brouwer, fixed-point theorem,Amer. Math. Month. 86 (1979) 818?827.","journal-title":"Amer. Math. Month."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A. V. Goldberg","year":"1989","unstructured":"A. V. Goldberg., S. V. Plotkin andG. E. Shannon: Parallel symmetry-breaking in sparsed graphs,SIAM J. Disc. Math. 1 (1989) 434?446.","journal-title":"SIAM J. Disc. Math."},{"key":"CR12","first-page":"285","volume":"31","author":"C. Kaklamanis","year":"1990","unstructured":"C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C., Thomborson, A. Tsantilas: Asymptotically tight bounds for computing with faulty arrays of processors,FOCS 31 (1990), 285?296.","journal-title":"FOCS"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"N. Linial: Locality in distributed graph alorithms,SIAM Journal on Computing,21 (1992) 193?201., Preliminary version: N. Linial, Distributive algorithmsglobal solutions from local data,FOCS 28 (1987), 331?335.","journal-title":"SIAM Journal on Computing"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby: A simple parallel algorithm for the maximal independent set problem,SIAM J. on Computing,15 (1986) 1036?1053.","journal-title":"SIAM J. on Computing"},{"key":"CR15","volume-title":"Algebraic Topology","author":"E. H. Spanier","year":"1966","unstructured":"E. H. Spanier:Algebraic Topology, McGraw-Hill, New York, 1966."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"M. Todd:The computation of fixed points and applications, Lecture Notes in Econnomics and Mathematical Systems, 124, Springer-Verlag, 1976.","DOI":"10.1007\/978-3-642-50327-6"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1007\/BF02765904","volume":"66","author":"B. Weiss","year":"1989","unstructured":"B. Weiss: A combinatorial proof of the Borsuk-Ulam antipodal point theorem,Israel J. Math. 66 (1989) 364?368.","journal-title":"Israel J. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303516.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01303516\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01303516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:55:40Z","timestamp":1586181340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01303516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF01303516"],"URL":"https:\/\/doi.org\/10.1007\/bf01303516","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}