A class of ball-and-bin problems and its application to mesh networks

Author

Sarbazi-Azad, H. ; Khonsari, A.

Author_Institution

Dept. of Comput. Eng., Sharif Univ. of Technol., Tehran, Iran

Volume

3

fYear

2003

fDate

14-17 Dec. 2003

Firstpage

1038

Abstract

Non-recursive and explicit expressions for calculating the number of ways to distribute n indistinguishable balls into m distinguishable bins with different capacities have been derived. Similar expression for the special case where bins have the same capacity was previously reported in the literature. Theses expressions can be used to study network graphs with grid structures. In this line, we have derived some topological properties of meshes, furnishing some expressions to calculate the surface area and volume of radial spheres in the mesh network.

Keywords

combinatorial mathematics; multiprocessor interconnection networks; network topology; trees (mathematics); ball-and-bin problems; collective communication operations; combinatorial properties; different capacities; distinguishable bins; grid structures; indistinguishable balls; mesh networks; network graphs; nonrecursive explicit expressions; radial spheres; resource placement; spanning trees; surface area; topological properties; Application software; Computer networks; Computer science; Mathematics; Mesh networks; Network topology; Parallel machines; Physics; Tree data structures; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Electronics, Circuits and Systems, 2003. ICECS 2003. Proceedings of the 2003 10th IEEE International Conference on

Print_ISBN

0-7803-8163-7

Type

conf

DOI

10.1109/ICECS.2003.1301687

Filename

1301687