On bottleneck partitioning of k-ARY n-cubes

David M. Nicol, Weizhen Mao

Research output: Contribution to journalArticlepeer-review


Graph partitioning is a topic of extensive interest, with applications to parallel processing. In this context graph nodes typically represent computation, and edges represent communication. One seeks to distribute the workload by partitioning the graph so that every processor has approximately the same workload, and the communication cost (measured as a function of edges exposed by the partition) is minimized. Measures of partition quality vary; in this paper we consider a processor's cost to be the sum of its computation and communication costs, and consider the cost of a partition to be the bottleneck, or maximal processor cost induced by the partition. For a general graph the problem of finding an optimal partitioning is intractable. In this paper we restrict our attention to the class of k-ary n-cube graphs with uniformly weighted nodes. Given mild restrictions on the node weight and number of processors,.we identify partitions yielding the smallest bottleneck. We also demonstrate by example that some restrictions are necessary for the partitions we identify to be optimal. In particular, there exist cases where partitions that evenly partition nodes need not be optimal.

Original languageEnglish (US)
Pages (from-to)389-399
Number of pages11
JournalParallel Processing Letters
Issue number3
StatePublished - 1996
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'On bottleneck partitioning of k-ARY n-cubes'. Together they form a unique fingerprint.

Cite this