{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:26:03Z","timestamp":1759335963462},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,2]]},"abstract":"<jats:p>This paper deals with two kinds of generalized hypercubes: a d-dimensional c-ary clique [Formula: see text] and a d-dimensional c-ary array [Formula: see text]. A d-dimensional c-ary clique [Formula: see text] has nodes labeled by c<jats:sup>d<\/jats:sup>integers from 0 to c<jats:sup>d<\/jats:sup>- 1 and two nodes are connected by an edge if and only if the c-ary representations of their labels differ by one and only one digit. A d-dimensional c-ary array [Formula: see text] also has nodes labeled by c<jats:sup>d<\/jats:sup>integers from 0 to c<jats:sup>d<\/jats:sup>- 1, and two nodes are connected if and only if the c-ary representations of their labels differ by one and only one digit and the absolute value of the difference in that digit is 1. Further, an n-node c-ary clique [Formula: see text] is the induced subgraph of [Formula: see text] with nodes labeled by integers from 0 to n - 1. The main contribution of this paper is to clarify several topological properties of [Formula: see text] and [Formula: see text] in terms of their linear layouts. For this purpose, we first prove that [Formula: see text] is a maximum subgraph of [Formula: see text], that is, [Formula: see text]has the largest number of edges over all n-node subgraphs of [Formula: see text], whenever n \u2264 m. Using this fact, we show the exact values of the bisection width, cut width, and total edge length of [Formula: see text]. We also show the exact value of the bisection width of [Formula: see text] and nearly tight values of the cut width and the total edge length of [Formula: see text].<\/jats:p>","DOI":"10.1142\/s0129054103001637","type":"journal-article","created":{"date-parts":[[2003,6,25]],"date-time":"2003-06-25T00:53:09Z","timestamp":1056502389000},"page":"137-156","source":"Crossref","is-referenced-by-count":16,"title":["LINEAR LAYOUT OF GENERALIZED HYPERCUBES"],"prefix":"10.1142","volume":"14","author":[{"given":"KOJI","family":"NAKANO","sequence":"first","affiliation":[{"name":"School of Information Science, Japan Advanced Institute of Science and Technology, Tatsunokuchi, Ishikawa 923-1292, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Parallel Sorting Algorithms","author":"Akl S. G.","year":"1985"},{"key":"rf2","volume-title":"The Design and Analysis of Parallel Algorithms","author":"Akl S. G.","year":"1989"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000216"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00162-4"},{"key":"rf7","volume":"33","author":"Bhuyan L. N.","journal-title":"IEEE Transactions on Computers"},{"key":"rf8","unstructured":"G.\u00a0Brebner, VLSI: Algorithms and Architectures, eds. P.\u00a0Bertolazii and F.\u00a0Luccio (Elsevier Science Publishers B.V.(North-Holland), 1985)\u00a0pp. 221\u2013231."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/12.53599"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/359361.359447"},{"key":"rf11","author":"Diaz J.","journal-title":"ACM Computing Surveys"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/0112012"},{"key":"rf14","volume-title":"Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks","author":"Leighton F. T.","year":"1983"},{"key":"rf15","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes","author":"Leighton F. T.","year":"1992"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90016-4"},{"key":"rf17","first-page":"647","volume":"76","author":"Manabe Y.","journal-title":"Trans. IEICE(D) Japan"},{"key":"rf18","first-page":"856","volume":"73","author":"Nakano K.","journal-title":"IEICE Transactions"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"475","DOI":"10.21136\/CMJ.1981.101762","volume":"31","author":"Niepel L.","journal-title":"Czechoslovak Mathematical Journal"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1137\/0204038"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90215-4"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,8]],"date-time":"2021-06-08T05:20:16Z","timestamp":1623129616000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":18,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,2]]}},"alternative-id":["10.1142\/S0129054103001637"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001637","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}