This book provides the most basic combinatorial problems and well-established theory in design and analysis of the topological structure of interconnection networks in the graph-theoretic language. It covers the basic methods of network design,several well-known networks such as hypercubes,de Bruijn digraphs,Kautz digraphs,double loop,and the newest parameters to measure performance of networks such as forwarding indices of a routing,Menger number,Rabin number,fault-tolerant diameter,wide-diameter,generalized dominating number,and restricted connectivity. It will be of significant interest to researchers and practitioners working in design and analysis of networks,particularly to undergraduates and postgraduates specializing in computer science and applied mathematics.
样章试读
暂时还没有任何用户评论
全部咨询(共0条问答)
暂时还没有任何用户咨询内容
目录
Preface Part Ⅰ Networks and Graphs Chapter 1 Fundamentals of Networks and Graphs 1.1 Graphs and Networks 1.2 Basic Concepts and Notations 1.3 Trees and Planar Graphs 1.4 Transmission Delay and Diameter 1.5 Fault Tolerance and Connectivity 1.6 Embedding and Routings 1.7 Basic Principles of Network Design Exercises Chapter 2 Symmetry of Graphs or Networks 2.1 Fundamentals on Groups 2.2 Vertex-Transitive Graphs 2.3 Edge-Transitive Graphs 2.4 Atoms of Graphs 2.5 Connectivity of Transitive Graphs Exercises Part Ⅱ Basic Methods of Network Designs Chapter 3 Line Graphical Methods 3.1 Line Graphs and Basic Properties 3.2 Basic Properties of Line Digraphs 3.3 Iterated Line Graphs 3.4 Connectivity of Line Graphs Exercises Chapter 4 Cayley Methods 4.1 Cayley Graphs 4.2 Transitivity of Cayley Graphs 4.3 Atoms and Connectivity of Cayley Graphs 4.4 Vertex-Transitive Graphs with Prime Order Exercises Chapter 5 Cartesian Product Methods 5.1 Cartesian Product of Graphs 5.2 Diameter and Connectivity 5.3 Other Properties of Cartesian Products 5.4 Generalized Cartesian Products Exercises Chapter 6 Basic Problems in Optimal Designs 6.1 Undirected(d,k)-Graph Problems 6.2 Directed(d,k)-Graph Problems 6.3 Relations between Diameter and Connectivity Exercises Part Ⅲ Well-Known Topologies of Networks Chapter 7 Hypercube Networks 7.1 Definitions and Basic Properties 7.2 Gray Codes and Cycles 7.3 Lengths of Paths 7.4 Embedding Problems 7.5 Generalized Hypercubes 7.6 Some Variations of Hypercubes Exercises Chapter 8 De Bruijn Networks 8.1 Definitions and Basic Properties 8.2 Uniqueness of Shortest Paths 8.3 Generalized de Bruijn Digraphs 8.4 Comparison with Hypercubes Exercises Chapter 9 Kautz Networks 9.1 Definitions and Basic Properties 9.2 Generalized Kautz Digraphs 9.3 Connectivity of Generalized Kautz Digraphs Exercises Chapter 10 Double Loop Networks 10.1 Double Loop Networks 10.2 L-Tiles in the Plane 10.3 L-Tiles and Double Loop Networks 10.4 Design of Optimal Double Loop Networks 10.5 Basic Properties of Circulant Networks Exercises Chapter 11 Topologies of Other Networks 11.1 Mesh Networks and Grid Networks 11.2 Pyramid Networks 11.3 Cube-Connected Cycles 11.4 Butterfly Networks 11.5 Bene* Networks 11.6 Ω Networks 11.7 Shuffle-Exchange Networks Exercises Part Ⅳ Fault-Tolerant Analysis of Networks Chapter 12 Routings in Networks 12.1 Forwarding Index of Routing 12.2 Edge-Forwarding Index of Routing 12.3 Forwarding Indices of Some Graphs 12.4 Delay of Fault-Tolerant Routing Exercises Chapter 13 Fault-Tolerant Diameters in Networks 13.1 Diameters of Altered Graphs 13.2 Edge Fault-Tolerant Diameters 13.3 Relations between Two Diameters 13.4 Vertex Fault-Tolerant Diameters 13.5 Fault-Tolerant Diameter of Product Graphs 13.6 Fault-Tolerant Diameters of Some Networks Exercises Chapter 14 Menger-Type Problems in Parallel Systems 14.1 Menger-Type Problems 14.2 Bounded Menger Number and Connectivity 14.3 Bounded Edge-Connectivity 14.4 Rabin Numbers of Networks Exercises Chapter 15 Wide-Diameters of Networks 15.1 Wide-Diameter and Basic Results 15.2 Wide-Diameter of Regular Graphs 15.3 Wide-Diameter of Cartesian Products 15.4 Wide-Diameter and Independence Number 15.5 Wide-Diameter and Fault-Tolerant Diameter 15.6 Wide-Diameters of Some Networks Exercises Chapter 16 Generalized Independence and Domination Numbers 16.1 Generalized Independence Numbers 16.2 Generalized Domination Numbers 16.3 Distance Independence and Domination Exercises Chapter 17 Restricted Fault-Tolerance of Networks 17.1 Restricted Connectivity and Diameter 17.2 Restricted Edge-Connectivity 17.3 Restricted Edge-Atoms 17.4 Results on Transitive Graphs 17.5 Super Connectivity of Networks 17.6 Super Edge-Connectivity of Networks 17.7 Super Connectivity of Line Graphs 17.8 Connectivity Restricted by Degree-Conditions 17.9 Connectivity Restricted by Order-Conditions 17.10 Restricted Connectivity of Some Networks Exercises Bibliography A List of Notations Index
京公网安备 11010102004214号