Premium
Constrained length connectivity and survivable networks
Author(s) -
Ameur Walid Ben
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200008)36:1<17::aid-net3>3.0.co;2-z
Subject(s) - combinatorics , infimum and supremum , disjoint sets , path length , mathematics , path (computing) , node (physics) , constant (computer programming) , discrete mathematics , computer science , physics , computer network , quantum mechanics , programming language
Some problems related to constrained length connectivity are addressed in this paper. Let S l ( x, y ) be the minimum number of vertices that should be removed to destroy all the paths of length at most l between two vertices x and y . Let I l ( x, y ) be the maximum number of such node‐disjoint paths. We first focus on f ( l, d ), defined as the supremum of ( S l ( x, y ))/( I l ( x, y )) taken over all graphs and all pairs of x, y separated by a distance d . One of the results shown in this paper states that this supremum is exactly equal to l + 1 − d when d ≥ ⌈⅔ l + 1)⌉ and is at least constant when 2 ≤ d ≤ 2 + ⌊( l + 1)/3⌋. Some classes of two connected graphs satisfying path‐length constraints are defined. Most of them describe survivable telecommunication networks. Relationships between flows and constrained length connectivity are addressed. We also study the minimum edge numbers of these two connected graphs. Some of their topological properties are presented. © 2000 John Wiley & Sons, Inc.