On k-ary n-cubes: Theory and applications

Weizhen Mao, David M. Nicol

Research output: Contribution to journalArticlepeer-review


Many parallel processing applications have communication patterns that can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and tori. In this paper, combinatorial properties of k-ary n-cubes are examined. In particular, the problem of characterizing the subgraph of a given number of nodes with the maximum edge count is studied. These theoretical results are then applied to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions.

Original languageEnglish (US)
Pages (from-to)171-193
Number of pages23
JournalDiscrete Applied Mathematics
Issue number1
StatePublished - Jun 15 2003
Externally publishedYes


  • Communication
  • Graph partitioning
  • Parallel processing
  • k-ary n-cubes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On k-ary n-cubes: Theory and applications'. Together they form a unique fingerprint.

Cite this