{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:47:13Z","timestamp":1648810033901},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,2,1]],"date-time":"1997-02-01T00:00:00Z","timestamp":854755200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory of Computing Systems"],"published-print":{"date-parts":[[1997,2]]},"DOI":"10.1007\/bf02679452","type":"journal-article","created":{"date-parts":[[2007,7,28]],"date-time":"2007-07-28T04:56:42Z","timestamp":1185598602000},"page":"39-49","source":"Crossref","is-referenced-by-count":1,"title":["New graph decompositions with applications to emulations"],"prefix":"10.1007","volume":"30","author":[{"given":"C.","family":"Kaklamanis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,30]]},"reference":[{"key":"BF02679452_CR1","unstructured":"A. Agrawal, P. Klein, S. Rao, and R. Ravi. Approximation through multicommodity flow.Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 726\u2013737, October 1989."},{"key":"BF02679452_CR2","doi-asserted-by":"crossref","unstructured":"W. Aiello and T. Leighton. Coding theory, hypercube embeddings, and fault tolerance.Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 125\u2013136, July 1991.","DOI":"10.1145\/113379.113391"},{"key":"BF02679452_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Seymour, and R. Thomas. A separator theorem for graphs with an excluded minor and its applications.Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 293\u2013299, May 1990.","DOI":"10.1145\/100216.100254"},{"key":"BF02679452_CR4","unstructured":"B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Fast constructions of sparse neighborhood covers. Unpublished manuscript."},{"key":"BF02679452_CR5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and D. Peleg. Sparse partitions. Proceedings of the 31st Symposium on Foundations of Computer Science, pages 503\u2013513, 1990.","DOI":"10.1109\/FSCS.1990.89571"},{"key":"BF02679452_CR6","doi-asserted-by":"crossref","first-page":"1641","DOI":"10.1002\/j.1538-7305.1964.tb04103.x","volume":"43","author":"V. E. Bene\u0161","year":"1964","unstructured":"V. E. Bene\u0161. Optimal rearrangeable multistage connecting networks.Bell System Technical Journal, 43:1641\u20131656, July 1964.","journal-title":"Bell System Technical Journal"},{"key":"BF02679452_CR7","doi-asserted-by":"crossref","unstructured":"S. Bhatt, F. Chung, T. Leighton, and A. Rosenberg. Optimal simulations of tree machines.Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 274\u2013282, October 1986.","DOI":"10.1109\/SFCS.1986.38"},{"key":"BF02679452_CR8","doi-asserted-by":"crossref","unstructured":"S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems.Journal of Computer and System Sciences, 28(2), 1984.","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"BF02679452_CR9","first-page":"17","volume-title":"Paths, Flows, and VLSI-Layout","author":"F. R. K. Chung","year":"1990","unstructured":"F. R. K. Chung. Separator theorems and their applications. In B. Korte, L. Lovasz, H. J. Promel, and A. Schriver, editors,Paths, Flows, and VLSI-Layout, pages 17\u201334. Springer-Verlag, New York, 1990."},{"key":"BF02679452_CR10","doi-asserted-by":"crossref","unstructured":"R. Cole, B. Maggs, and R. Sitaraman. Multi-scale self-simulation: A technique for reconfiguring arrays with faults.Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 561\u2013572, May 1993.","DOI":"10.1145\/167088.167235"},{"key":"BF02679452_CR11","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1137\/0603022","volume":"3","author":"H. N. Djidjev","year":"1982","unstructured":"H. N. Djidjev. On the problem of partitioning planar graphs.SIAM Journal of Algebraic and Discrete Methods, 3:229\u2013241, 1982.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"BF02679452_CR12","volume-title":"Encoding Graphs in Graphs","author":"M. R. Fellows","year":"1985","unstructured":"M. R. Fellows. Encoding Graphs in Graphs. Ph.D. thesis, Department of Computer Science, University of California, San Diego, CA, 1985."},{"key":"BF02679452_CR13","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Rao, and S. Plotkin. Excluded minors, network decomposition, and multicommodity flow.Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 682\u2013690, May 1993.","DOI":"10.1145\/167088.167261"},{"key":"BF02679452_CR14","doi-asserted-by":"crossref","unstructured":"R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg. Work-preserving emulations of fixed-connection networks.Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 227\u2013240, May 1989.","DOI":"10.21236\/ADA211915"},{"key":"BF02679452_CR15","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, B. Maggs, and S. Rao. Universal rounding algorithms.Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 256\u2013269, 1988.","DOI":"10.1109\/SFCS.1988.21942"},{"key":"BF02679452_CR16","doi-asserted-by":"crossref","unstructured":"T. Leighton, B. Maggs, and R. Sitaraman. On the fault tolerance of some popular bounded-degree networks.Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 542\u2013552, October 1992.","DOI":"10.1109\/SFCS.1992.267797"},{"key":"BF02679452_CR17","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson. Area-efficient layouts (for VSLI).Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pages 270\u2013281, October 1980.","DOI":"10.1109\/SFCS.1980.13"},{"key":"BF02679452_CR18","volume-title":"Area Efficient VLSI Computation","author":"C. E. Leiserson","year":"1983","unstructured":"C. E. Leiserson.Area Efficient VLSI Computation. MIT Press, Cambridge, MA, 1983."},{"issue":"10","key":"BF02679452_CR19","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/TC.1985.6312192","volume":"34","author":"C. E. Leiserson","year":"1985","unstructured":"C. E. Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing.IEEE Transactions on Computers, 34(10):892\u2013901, October 1985.","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"BF02679452_CR20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"8","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs.SIAM Journal of Applied Mathematics, 8(2):177\u2013189, April 1979.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"BF02679452_CR21","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00265559","volume":"19","author":"F. Meyer","year":"1983","unstructured":"F. Meyer and der Heide. Efficiency of universal parallel computers.Acta Informatica, 19:269\u2013296, 1983.","journal-title":"Acta Informatica"},{"key":"BF02679452_CR22","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1137\/0215008","volume":"15","author":"F. Meyer","year":"1989","unstructured":"F. Meyer and der Heide. Efficient simulations among several models of parallel computers.SIAM Journal of Computing, 15:106\u2013119, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"BF02679452_CR23","doi-asserted-by":"crossref","unstructured":"G. L. Miller, S.-H. Teng, and S. A. Vavasis. A unified geometric approach to graph separators.Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 538\u2013547, 1991.","DOI":"10.1109\/SFCS.1991.185417"},{"key":"BF02679452_CR24","unstructured":"S. Plotkin, S. Rao, and W. Smith. Shallow excluded minors and improved graph decompositions.Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 462\u2013470, January 1994."},{"key":"BF02679452_CR25","doi-asserted-by":"crossref","unstructured":"S. Rao. Faster algorithms for finding small separators in planar graphs.Proceedings of the 24th Annual ACM Symposium on Theory of Computing, Pages 229\u2013240, May 1992.","DOI":"10.1145\/129712.129735"},{"key":"BF02679452_CR26","doi-asserted-by":"crossref","unstructured":"E. J. Schwabe. On the computational equivalence of hypercube-derived networks.Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 388\u2013397, July 1990.","DOI":"10.1145\/97444.97706"},{"issue":"2","key":"BF02679452_CR27","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L. Valiant","year":"1981","unstructured":"L. Valiant. Universality considerations in VLSI circuits.IEEE Transactions on Computers, 30(2): 135\u2013140, February 1981.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679452.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02679452\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02679452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T11:40:47Z","timestamp":1558352447000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02679452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,2]]}},"alternative-id":["BF02679452"],"URL":"https:\/\/doi.org\/10.1007\/bf02679452","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}