Design of Survivable Networks
The problem of designing a cost-efficient network that survives the failure of one or more nodes or edges of the network is critical to modern telecommunications engineering. The method developed in this book is designed to solve such problems to optimali
- PDF / 18,124,964 Bytes
- 203 Pages / 468 x 684 pts Page_size
- 69 Downloads / 200 Views
1531
Lecture Notes in Mathematics Editors: A. Dold, Heidelberg B. Eckmann, ZUrich F. Takens, Groningen
1531
Mechthild Stoer
Design of Survivable Networks
Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest
Author Mechthild Stoer Konrad-Zuse-Zentrum fur Informationstechnik Berlin Heilbronner Str. lO W-1000 Berlin 31, Germany
Mathematics Subject Classification (1991): 90C35, 94C15, 05C40, 90C27
ISBN 3-540-56271-0 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-56271-0 Springer-Verlag New York Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer- Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1992 Printed in Germany Typesetting: Camera ready by author 46/3140-543210 - Printed on acid-free paper
Contents 1
Motivation
2
Network Survivability Models Using Node Types 2.1 Survivable Telephone Networks ........... 2.2 Graph-theoretic Formulation. . . . . . . . . . . . . 2.3 Integer LP-Formulation and Associated Polyhedra. 2.4 An Outline of the Cutting Plane Procedure. 2.5 Outlook on the Contents . . . . . . . . . . . . . . .
7 7 9 14 16 17
3
Survivable Network Design under Connectivity Constraints a Survey 3.1 Polynomially Solvable Cases 3.2 Results for Restricted Costs 3.3 Heuristics for General Costs 3.4 Exact Algorithms for General Costs .
19 21 25 27 30
5
Decomposition 4.1 Bridges, Articulation Nodes, and Paths 4.2 Articulation Sets of Size 2 for 2NCON 4.3 Articulation Sets of Size 2 for lECON 4.4 Cutsets of Size 3 for 2CON . 4.5 Cutsets of Size k for kCON
33
5
Basic Inequalities 5.1 Dimension and Trivial Inequalities. 5.2 Cut Constraints for Low-Connectivity. 5.3 Cut Constraints for kECON ..... 5.4 Node Cut Constraints for 2NCON .. 5.5 (Node) Cut Constraints for kNCON .
49 49 51 55 63 66
6
Lifting Theorems 6.1 Expansion of Nodes. 6.2 Addition of Edges . . 6.3 Addition of Nodes of Type 1
69 70 73 74
4
34 34 36 40 44
CONTENTS
2 7 Partition Inequalities 7.1 Motivation . . . . . 7.2 Facet Results for kECON 7.3 Facet Results for kNCON 7.4 Facet Results for Low Connectivity
77 77 79 85 88
8
Node Partition Inequalities 8.1 Generalization of Node Cut Constraints. 8.2 Validity . . . 8.3 Facet Results . . . . . . .
91 91 93 94
9
Lifted r-Cover Inequalities 9.1 Motivation . 9.2 r-Cover Inequalities. . . . 9.3 Lifted r-Cover Inequalities
101
10 Comb Inequalities 10.1 Comb Inequalities for 2NCON 10.2 Comb Inequalities for kNCON 10.3 Comb Inequalities for 2ECON
113
11 How to Find Valid Inequalities 11.1 Rel
Data Loading...
