|
Course No:
S07010461
Credit: 4 Periods: 80
Combinatorial
Network
Theory
Required
textbook: Junming Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic
Publishers, October, 2001
Background
of Course:
The
advent of very large scale integrated (VLSI) circuit technology has enabled the
construction of very complex and large interconnection networks. By most
accounts, the next generation of supercomputers will achieve its gains by
increasing the number of processing elements, rather than by using faster
processors. The most difficult technical problem in constructing a supercomputer
will be the design of the interconnection network through which the processors
communicate. Selecting an appropriate and adequate topological structure of
interconnection networks will become a critical issue. Graph theory is a
fundamental and powerful mathematical tool for designing and analyzing
interconnection networks, since an interconnection network is able to be
represented as a graph whose vertices represent components of the network and
whose edges represent physical communication links. Such a graph is called the
topological structure of the interconnection network. Thus, we may enjoy the
methods in graph theory to study the structure of networks, on which many
research efforts have been made over the past decade.
Course
Description: This
course provides the most basic problems, concepts, and well-established results
from the topological structure interconnection networks in the graph-theoretic
language. It covers the basic principles and methods of network design, several
well-known networks such as hypercube, de Bruijn digraph, Kautz digraph, double
loop, and others, and the newest parameters to measure performance of
fault-tolerant networks such as forwarding index of a routing, Menger number,
Rabin number, fault-tolerant diameter, wide-diameter, restricted connectivity
and diameter, and (l, w)-dominating number.
Audience:
Postgraduate
Students (Ph. D and M. S)
Preparatory Courses:
Abstract
Algebra, Combinatorics, Graph Theory
Test Form:
Written
Examination
|
|
