Combinatorial Network Theory
A basic problem for the interconnection of communications media is to design interconnection networks for specific needs. For example, to minimize delay and to maximize reliability, networks are required that have minimum diameter and maximum connectivity
- PDF / 15,778,911 Bytes
- 219 Pages / 439 x 666 pts Page_size
- 56 Downloads / 207 Views
Applied Optimization Volume 1
The titles published in this series are listed at the end ofthis volume.
Combinatorial Network Theory Edited by
Ding-Zhu Du University 01Minnesota
and
D. FrankHsu Fordham University
Springer-Science+Business Media, B.V.
Library of Congress Cataloging-in-Publication Data Cambinatarial netwark theary / edited by Din-Zhu Du and D. Frank Hsu. p. cm. -- (Appl ied aptimizatian ; val. 1) 1. Netwark analysis (Planning) 2. Cambinatarial analysis. I. Du, Dingzhu. 11. Hsu, D. Frank (Derbiau Frank), 1948III. Series. T57.85.C65 1995 511' .5--dc20 95-41542
ISBN 978-1-4419-4752-9
ISBN 978-1-4757-2491-2 (eBook)
DOI 10.1007/978-1-4757-2491-2
Printed on acid-free paper
All Rights Reserved © 1996 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1996. Softcover reprint of the hardcover 1st edition 1996 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
CONTENTS
PREFACE 1
2
3
vii
ADDITIVE GROUP THEORY APPLIED TO NETWORK TOPOLOGY
1
Y. O. Harnidoune 1.1 Introduction 1.2 Basic Notions 1.3 The Finite (a + ß)- Theorems 1.4 The Critical Pair Problem 1.5 Kneser's Theorem and Some Applications 1.6 Bases of Finite Abellian Groups
20 28 32
CONNECTIVITY OF CAYLEY DIGRAPHS
41
Ralph Tindell 2.1 Introduction 2.2 Terminology and Definitions 2.3 Edge- Connectivity 2.4 Connectivity and Atoms
41 41 46 54
DE BRUIJN DIGRAPHS, KAUTZ DIGRAPHS, AND THEIR GENERALIZATIONS
65
Ding-Zhu Du, Feng Cao, D. Frank Hsu 3.1 Introduction 3.2 Generalizations 3.3 Diameter 3.4 Line Connectivity 3.5 Connectivity 3.6 Super Line-Connectivity 3.7 Hamiltonian Property
65 71 76 78 86 94 96
v
1 3 11
vi
4
5
LINK-CONNECTIVITIES OF EXTENDED DOUBLE LOOP NETWORKS
107
Frank K. Hwang 4.1 Introduction 4.2 Proof of Th eorem 4.1.2 4.3 P repar ation for t he Proof of Theorem 4.1.1 4.4 P roof of Th eorem 4.1.1 4.5 Conclusion
107 111 113 116 123
DISSEMINATION OF INFORMATION IN INTERCONNECTION NETWORKS (BROADCASTING & GOSSIPING)
125
Juraj Hromkovic, Ralf Klasing, Burkhard Monien , Regine Peine 5.1 Introduction 5.2 Broadcastin g 5.3 Gossiping 5.4 Ot her Modes and Complexity Measures
125 146 170 206
PREFACE
Recently the interest in the interconnection of communication has grown rapidly. One of the basic problems is to design optimal interconnection networks for certain needs. For example, to minimize the communication delay and to maximize the reliability, one looks for networks with minimum diameter and maximum connectivity under certain conditions. This small book consists of five chapters: Chapter 1: Additive Group Tbeory Applied to Network Topology by Y.O. Hamidoune Chapter 2, Connectivity of Cayley Digraphs by Ralph Tindell Chapter 3, De Bruijn Digraphs, Kautz Digraphs, and Their Generalizations by Ding-Zhu Du, Feng Cao, and D. Frank Hsu C
Data Loading...
