{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T10:29:44Z","timestamp":1648981784132},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1997,9]]},"abstract":"<jats:p> Index-shuffle graphs are introduced as candidate interconnection networks for parallel computers. The comparative advantages of index-shuffle graphs over the standard bounded-degree \"approximations\" of the hypercube, namely butterfly-like and shuffle-like graphs, are demonstrated in the theoretical framework of graph embedding and network emulations. <\/jats:p><jats:p> An N-node index-shuffle graph emulates: <\/jats:p><jats:p> \u2022 an N-node shuffle-exchange graph with no slowdown, which the currently best emulations of shuffle-like graphs by hypercubes and butterflies incur a slowdown of \u03a9( log N). <\/jats:p><jats:p> \u2022 its like-sized butterfly graph with a slowdown O( log log log N), while the currently best emulations of butterfly-like graphs by shuffle-like graphs incur a slowdown of \u03a9( log log N). <\/jats:p><jats:p> \u2022 an N-node hypercube that executes an on-line leveled algorithm with a slowdown O( log log N), while the slowdown of currently best such emulations of the hypercube by its bounded-degree shuffle-like and butterfly-like derivatives remains \u03a9( log N). Our emulation is based on an embedding of an N-node hypercube into an N-node index-shuffle graph with dilation O( log log N), while the currently best embeddings of the hypercube into its bounded-degree shuffle-like and butterfly-like derivatives incur a dilation of \u03a9( log N). <\/jats:p>","DOI":"10.1142\/s0129054197000197","type":"journal-article","created":{"date-parts":[[2003,10,16]],"date-time":"2003-10-16T00:35:19Z","timestamp":1066264519000},"page":"289-304","source":"Crossref","is-referenced-by-count":2,"title":["Index-Shuffle Graphs"],"prefix":"10.1142","volume":"08","author":[{"given":"Marc","family":"Baumslag","sequence":"first","affiliation":[{"name":"Bear, Stearns, &amp; Co. Inc., 245 Park Avenue, New York, NY 10167, USA"}]},{"given":"Bojana","family":"Obreni\u0107","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Queens College and Graduate Center of CUNY, Flushing, NY 11367, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054197000197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:46:00Z","timestamp":1565138760000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054197000197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,9]]}},"alternative-id":["10.1142\/S0129054197000197"],"URL":"https:\/\/doi.org\/10.1142\/s0129054197000197","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,9]]}}}