{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:48:04Z","timestamp":1648882084222},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1989,12,1]],"date-time":"1989-12-01T00:00:00Z","timestamp":628473600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[1989,12]]},"DOI":"10.1007\/bf01381720","type":"journal-article","created":{"date-parts":[[2005,4,2]],"date-time":"2005-04-02T00:35:33Z","timestamp":1112402133000},"page":"505-549","source":"Crossref","is-referenced-by-count":13,"title":["Hypercube embedding heuristics: An evaluation"],"prefix":"10.1007","volume":"18","author":[{"given":"Woei-Kae","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias F. M.","family":"Stallmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward F.","family":"Gehringer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/0743-7315(87)90018-9","volume":"4","author":"F. Berman","year":"1987","unstructured":"F. Berman and L. Snyder, On mapping parallel algorithms into parallel architectures,J. of Parallel and Distributed Computing,4:439?458 (1987).","journal-title":"J. of Parallel and Distributed Computing"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/TC.1984.1676437","volume":"33","author":"L. Bhuyan","year":"1984","unstructured":"L. Bhuyan and D. P. Agrawal, Generalized hypercube and hyperbus structures for a computer network,IEEE Transactions on Computers,C-33:323?333 (1984).","journal-title":"IEEE Transactions on Computers, C"},{"key":"CR3","unstructured":"W. Hillis,The Connection Machine, MIT Press (1985)."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Y. Saad and M. H. Schultz, Topological properties of hypercubes,IEEE Transactions on Computers, Vol. C-37 (1988).","DOI":"10.1109\/12.2234"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/0743-7315(89)90033-6","volume":"7","author":"A. Wagner","year":"1989","unstructured":"A. Wagner, Embedding arbitrary binary trees in a hypercube,J. of Parallel and Distributed Computing,7:503?520 (1989).","journal-title":"J. of Parallel and Distributed Computing"},{"key":"CR6","unstructured":"INTEL Scientific Computers, Direct-Connecttm routing solves node communications challenge,iSCurrents, pp. 5?6 (1987)."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1145\/325096.325132","volume":"18","author":"D. Lenoski","year":"1990","unstructured":"D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta, and J. Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, ACM Computer Architecture News,18:148?159 (1990).","journal-title":"ACM Computer Architecture News"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/2.74","volume":"21","author":"L. W. Tucker","year":"1988","unstructured":"L. W. Tucker and G. G. Robertson, Architecture and applications of the Connection Machine,IEEE Computer,21:26?38 (1988).","journal-title":"IEEE Computer"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1145\/2157.322401","volume":"30","author":"J. Hong","year":"1983","unstructured":"J. Hong, K. Mehlhorn, and A. Rosenberg, Cost trade-offs in graph embeddings with applications,J. Assoc. Comput. Mach.,30:709?728 (1983).","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0020-0190(87)90090-1","volume":"25","author":"G. Cybenko","year":"1987","unstructured":"G. Cybenko, D. Krumme, and K. Venkataraman, Fixed hypercube embedding,Information Processing Letters,25:35?39 (1987).","journal-title":"Information Processing Letters"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1137\/0219038","volume":"19","author":"A. Wagner","year":"1990","unstructured":"A. Wagner and D. Corneil, Embedding trees in the hypercube isNP-complete,SIAM J. on Computing,19:570?590 (1990).","journal-title":"SIAM J. on Computing"},{"key":"CR12","unstructured":"F. Berman, Experience with an automatic solution to the mapping problem,The Characteristics of Parallel Algorithms, L. Jamieson, D. Gannon, and R. Douglas, (eds.), MIT Press (1987)."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1109\/TC.1981.1675756","volume":"30","author":"S. Bokhari","year":"1981","unstructured":"S. Bokhari, On the mapping problem,IEEE Transactions on Computers,C-30:207?214 (1981).","journal-title":"IEEE Transactions on Computers, C"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/TC.1987.1676984","volume":"36","author":"K. Fukunaga","year":"1987","unstructured":"K. Fukunaga, S. Yamada, and T. Kasai, Asignment of job modules onto array processors,IEEE Transactions on Computers,C-36:888?891 (1987).","journal-title":"IEEE Transactions on Computers, C"},{"key":"CR15","unstructured":"A. Gabriellian and D. Tyler, Optimal object allocation in distributed computer systems,Proc. Int'l Conf. on Distributed Computer Systems, pp. 88?95 (1984)."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0167-8191(87)90026-3","volume":"4","author":"H. M\ufffdhlenbein","year":"1987","unstructured":"H. M\ufffdhlenbein, M. Gorges-Schleuter, and O. Kr\ufffdmer, New solutions to the mapping problem of parallel systems: The evolution approach,Parallel Computing,4:269?279 (1987).","journal-title":"Parallel Computing"},{"key":"CR17","unstructured":"J. Ramanujam, F. Ercal, and P. Sadayappan, Task allocation by simulated annealing,Proc. Int'l Conf. on Supercomputing (1988)."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"1408","DOI":"10.1109\/TC.1987.5009494","volume":"36","author":"P. Sadayappan","year":"1987","unstructured":"P. Sadayappan and F. Ercal, Nearest-neighbor mapping of finite element graphs onto processor meshes,IEEE Trans. on Computers,C-36:1408?1424 (1987).","journal-title":"IEEE Trans. on Computers, C"},{"key":"CR19","unstructured":"K. Schwan and C. Gaimon, Automating resource allocation for theCm * multiprocessor,Proc. Int'l Conf. on Distributed Computer Systems, pp. 310?320 (1984)."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"W.-K. Chen and E. Gehringer, A graph-oriented mapping strategy for a hypercube,Proc. Third Conf. on Hypercube Concurrent Computers and Applications, pp. 200?209 (1988).","DOI":"10.1145\/62297.62322"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"F. Ercal, J. Ramanujam, and P. Sadayappan, Task allocation onto a hypercube by recursive mincut bipartitioning,J. of Parallel and Distributed Computing, to appear (1990).","DOI":"10.1016\/0743-7315(90)90004-9"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"F. Ercal and P. Sadayappan, One-to-one mapping process graphs onto a hypercube,Proc. Supercomputing '89, ACM, pp. 91?98 (1989).","DOI":"10.1145\/318789.318800"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0167-8191(89)90129-4","volume":"9","author":"O. Kr\ufffdmer","year":"1989","unstructured":"O. Kr\ufffdmer and H. M\ufffdhlenbein, Mapping strategies in message-based multiprocessor systems.Parallel Computing,9:213?225 (1989).","journal-title":"Parallel Computing"},{"key":"CR24","first-page":"433","volume":"36","author":"S.-Y. Lee","year":"1987","unstructured":"S.-Y. Lee and J. Aggarwal, A mapping strategy for parallel processing,IEEE Transactions on Computers,C-36:433?442 (1987).","journal-title":"IEEE Transactions on Computers, C"},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"M. Garey and R. Graham, On cubical graphs,J. of Combinatorial Theory, Vol. 18 (1975).","DOI":"10.1016\/0095-8956(75)90067-2"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/0020-0190(80)90025-3","volume":"11","author":"K. Bhat","year":"1980","unstructured":"K. Bhat, On the complexity of testing a graph forN-cube,Information Processing Letters,11:16?19 (1980).","journal-title":"Information Processing Letters"},{"key":"CR27","unstructured":"S. Bettayeb, z. Miller, and I. Sudborough, Embedding grids into hypercubes,VLSI Algorithms and Architectures: 3rd Aegean Workshop on Computing, Lecture Notes inComputer Science, Springer Verlag,319:201?211 (1988)."},{"key":"CR28","unstructured":"J. Brandenburg and D. Scott, Embedding of communication trees and grids into hypercubes, Technical Report 280182-001, INTEL Scientific Computers (1985)."},{"key":"CR29","first-page":"295","volume":"III","author":"M. Chan","year":"1988","unstructured":"M. Chan, Dilation-2 embeddings of grids into hypercubes,Proc. Int'l Conf. on Parallel Processing, Vol.III, pp. 295?298 (1988).","journal-title":"Proc. Int'l Conf. on Parallel Processing"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/0743-7315(85)90026-7","volume":"2","author":"A. Wu","year":"1985","unstructured":"A. Wu, Embedding of tree networks into hypercubes,J. of Parallel and Distributed Computing,2:238?249 (1985).","journal-title":"J. of Parallel and Distributed Computing"},{"key":"CR31","unstructured":"S. Bhatt, F. Chung, F. Leighton, and A. Rosenberg,Efficient embeddings of trees in hypercubes. Typescript, Department of Computer Science, Yale University, New Haven, Connecticut 06520."},{"key":"CR32","unstructured":"B. Monien and I. Sudborough, Simulating binary trees on hypercubes, inVLSI Algorithms and Architectures: 3rd Aegean Workshop on Computing, Lecture Notes inComputer Science, Springer Verlag,319:170?180 (1988)."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0019-9958(85)80012-7","volume":"66","author":"F. Afrati","year":"1985","unstructured":"F. Afrati, C. Papadimitriou, and G. Papageorgiou, The Complexity of cubical graphs,Information and Control,66:53?60 (1985).","journal-title":"Information and Control"},{"key":"CR34","doi-asserted-by":"crossref","unstructured":"B. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,Bell System Technical Journal, pp. 291?307 (1970).","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"CR35","first-page":"1","volume":"I","author":"S. Bollinger","year":"1988","unstructured":"S. Bollinger and S. Midkiff, Processor and link assignment in multiprocessors using simulated annealing,Proc. Int'l Conf. on Parallel Processing, Vol.I, pp. 1?7 (1988).","journal-title":"Proc. Int'l Conf. on Parallel Processing"},{"key":"CR36","first-page":"39","volume":"I","author":"F. Andr\ufffd","year":"1989","unstructured":"F. Andr\ufffd, J. Pazat, and T. Priol, Experiments with mapping algorithms on a hypercube,Proc. Fourth Conf. on Hypercubes, Concurrent Computers, and Applications, Vol. I, pp. 39?46 (1989).","journal-title":"Proc. Fourth Conf. on Hypercubes, Concurrent Computers, and Applications"},{"key":"CR37","unstructured":"J.-L. Pazat,Outils pour la Programmation d'un Multiprocesseur \ufffd M\ufffdmoires Distribu\ufffdes, Ph.D. thesis, Universit\ufffd de Bordeaux I (February 1989)."},{"key":"CR38","unstructured":"D. S. Johnson, C. R. Aragon, L. A. McGeogh, and C. Schevon,Optimization by simulated annealing: An experimental evaluation (Part I). Typescript."},{"key":"CR39","doi-asserted-by":"crossref","unstructured":"C. Fiduccia and R. Mattheyses, A linear-time heuristic for improving network partitions,Proc. 19th Design Automation Conf., pp. 175?181 (1982).","DOI":"10.1109\/DAC.1982.1585498"},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"W.-K. Chen, A graph-oriented mapping strategy for a hypercube, Master's thesis, North Carolina State University (1988).","DOI":"10.1145\/62297.62322"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1038\/scientificamerican0872-76","volume":"227","author":"F. Heath","year":"1972","unstructured":"F. Heath, Origins of the binary code,Scientific American,227:76?83 (1972).","journal-title":"Scientific American"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"S. Kirkpatrick, C. Gelatt, Jr., and M. Vecchi,Optimization by simulated annealing, Science, pp. 671?680 (1983).","DOI":"10.1126\/science.220.4598.671"},{"key":"CR43","unstructured":"W.-K. Chen and M. Stallmann, Local search variants for hypercube embedding,Proc. Fifth Distributed Memory Computing Conf., to appear (1990)."},{"key":"CR44","unstructured":"A. Wagner,Embedding Trees in a Hypercube, Ph.D. thesis, University of Toronto (1987)."}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01381720.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01381720\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01381720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T16:20:03Z","timestamp":1586190003000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01381720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["BF01381720"],"URL":"https:\/\/doi.org\/10.1007\/bf01381720","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}