Accession Number : ADA289711

Title :   On K-ARY N-CUBES: Theory and Applications.

Descriptive Note : Contract rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Mao, Weizhen ; Nicol, David M.

PDF Url : ADA289711

Report Date : OCT 1994

Pagination or Media Count : 30

Abstract : Many parallel processing networks can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and toruses. In this paper, combinatorial properties of k-ary n-cubes are explored. 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 used to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions. (AN)

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSING, *COMBINATORIAL ANALYSIS, OPTIMIZATION, COMPUTATIONS, COMPUTER COMMUNICATIONS, EDGES, GRAPHS, COMPUTER PROGRAMMING, COUNTING METHODS, NODES, BOUNDARIES, RECURSIVE FUNCTIONS, COMPUTER NETWORKS.

Subject Categories : Numerical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE