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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1994
Accession Number
ADA289711

Entities

People

  • David M. Nicol
  • Weizhen Mao

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Composite Materials
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Dynamic Programming
  • Engineering
  • Equations
  • Inequalities
  • Information Operations
  • Parallel Computing
  • Parallel Processing
  • Recursive Functions
  • Simulations
  • Trees (Data Structures)
  • Workload

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.