Topological Structure and Analysis of Interconnection Networks
==========================================================================
1.1
Graphs
and Interconnection Networks
1.1.1 Graphs
1.1.2 Interconnection Networks
1.1.3 Graph Isomorphism
1.2
Basic Concepts and Notations on Graphs
1.2.1 Subgraphs and Operations of Graphs
1.2.2 Degrees and Edge-Degrees
1.2.3 Paths, Cycles and Connected Graphs
1.2.4 Adjacency Matrices and Other Concepts
1.3
Trees, Embeddings and Planar Graphs
1.3.1 Trees and k-ary Trees
1.3.2 Embedding of Graphs
1.3.3 Planar Graphs and Layout of VLSI Circuits
1.4
Transmission Delay and Diameter
1.4.1 Diameter of Graphs
1.4.2 Average Distance of Graphs
1.4.3 Routings in Networks
1.5
Fault Tolerance and Connectivity
1.5.1 Menger's Theorem
1.5.2 Connectivity of Graphs
1.5.3 Fault Tolerance of Networks
1.6
Basic Principles of Network Design
1.6.1 Introduction
1.6.2 Basic Principles of Network Design
Chapter
2
Design
Methodology of Topological Structure of Interconnection Networks
2.1
Line Graphical Method
2.1.1 Line Graph of Undirected Graph
2.1.2 Line Graph of Digraph
2.1.3 Connectivity and Diameter of Line Graphs
2.1.4 Eulerian and Hamiltonian Properties
2.1.5 Iterated Line Digraphs
2.1.6 Edge-Connectivity of Line Graphs
2.2
Cayley Method
2.2.1 Vertex-Transitive Graphs
2.2.2 Edge-Transitive Graphs
2.2.3 Atoms of Graphs
2.2.4 Connectivity of Transitive Graphs
2.2.5 Cayley Graphs
2.2.6 Transitivity of Cayley Graphs
2.2.7 Atoms and Connectivity of Cayley Graphs
2.2.8 Vertex-Transitive Graphs with Prime Order
2.3
Cartesian Product Method
2.3.1 Cartesian Product of Undirected Graphs
2.3.2 Cartesian Product of Digraphs
2.3.3 Some Remarks on Cartesian Products
2.3.4 Diameter and Connectivity of Cartesian Products
2.3.5 Other Properties of Cartesian Products
2.3.6 Cartesian Product of Cayley Graphs
2.4
A Basic Problem in Optimal Design
2.4.1 Undirected (d, k)-Graph Problems
2.4.2 Directed (d, k)-Graph Problems
2.4.3 Bipartite (d, k)-Graph Problems
2.4.4 Planar (d, k)-Graph Problems
2.4.5 Relations between Diameter and Connectivity
3.1
Hypercube Networks
3.1.1 Two Equivalent Definitions
3.1.2 Some Basic Properties
3.1.3 Gray Codes and Cycles
3.1.4 Lengths of Paths
3.1.5 Embedding Problems
3.1.6 Generalized Hypercubes
3.1.7 Some Enhancements on Hypercubes
3.2
De Bruijn Networks
3.2.1 Three Equivalent Definitions
3.2.2 Eulerian and Hamiltonian Properties
3.2.3 Uniqueness of Shortest Paths
3.2.4 De Bruijn Undirected Graphs
3.2.5 Generalized de Bruijn Digraphs
3.2.6 Comparison with Hypercubes
3.3
Kautz Networks
3.3.1 Three Equivalent Definitions
3.3.2 Paths in Kautz Digraphs
3.3.3 Kautz Undirected Graphs
3.3.4 Generalized Kautz Digraphs
3.3.5 Connectivity of Generalized Kautz Digraphs
3.4
Double Loop Networks
3.4.1 Double Loop Networks
3.4.2 L-Tiles in the Plane
3.4.3 Diameter of Double Loop Networks
3.4.4 Optimal Design of Double Loop Networks
3.4.5 Circulant Networks and Basic Properties
3.5
Other Topological Structures of Networks
3.5.1 Mesh Networks and Grid Networks
3.5.2 Pyramid Networks
3.5.3 Cube-Connected Cycles
3.5.4 Butterfly Networks
3.5.5 Benes Networks
3.5.6 Omega Networks
3.5.7 Shuffle-Exchange Networks
4.1
Routings in Interconnection Networks
4.1.1 Forwarding Index of Routing
4.1.2 Edge-Forwarding Index of Routing
4.1.3 Delay of Fault-Tolerant Routing
4.1.4 Some Upper Bounds
4.2
Fault-Tolerant Diameter
4.2.1 Edge-Addition Problems
4.2.2 Edge-Deletion Problems
4.2.3 Vertex-Deletion Problems
4.2.4 Fault-Tolerant Diameters of Some Networks
4.3
Menger-Type Problems in Parallel Systems
4.3.1 Disjoint Paths for Bounded Length
4.3.2 Menger Number and Bounded Connectivity
4.3.3 Edge Disjoint Paths for Bounded Length
4.3.4 Disjoint Paths for Exceeded Length
4.3.5 Rabin Numbers of Networks
4.4
Wide Diameter of Networks
4.4.1 Containers and Basic Properties
4.4.2 Wide Diameter and Basic Results
4.4.3 Wide-Diameter on Regular Graphs
4.4.4 Wide-Diameter on Cartesian Products
4.4.5 Wide-Diameter and Independence Number
4.4.6 Wide-Diameter and Fault-Tolerant Diameter
4.4.7 Wide-Diameters of Some Well-Known Networks
4.4.8 Wide Diameter for Edge Variation
4.5
(l,w)-Independence and -Dominating Numbers
4.5.1 (l, w)-Independence Numbers
4.5.2 (l, w)-Dominating Numbers
4.5.3 (l,1)-Independence and -Dominating Numbers
4.5.4 Some (l, w)-Dominating Numbers
4.6
Restricted Fault-Tolerance of Networks
4.6.1 Restricted Connectivity and Diameter
4.6.2 Restricted Edge-Connectivity
4.6.3 Restricted Edge-Atoms
4.6.4 Restricted Edge-Connectivity of Transitive Graphs
4.6.5 Generalized Restricted Edge-Connectivity
Bibliography
List
of Symbols
Subject
Index
|
