Kenneth A. Berman

An edge-scheduled network N is a multigraph G = (V, E), where each edge e ϵ E has been assigned two real weights: a start time α(e) and a finish time β(e). Such a multigraph models a communication or transportation network. A multiedge joining vertices u and v represents a direct communication (transportation) link between u and v, and the edges of the multiedge represent potential communications (transportations) between u and v over a fixed period of time. For a, b ϵ V, and k a nonnegative integer, we say that N is k-failure ab-invulnerable for the time period [0, t] if information can be relayed from a to b within that time period, even if up to k edges are deleted, i.e., “fail.” The k-failure ab-vulnerability threshold νab(k) is the earliest time t such that N is k-failure ab-invulnerable for the time period [0, t] [where νab(k) = ∞ if no such t exists]. Let κ denote the smallest k such that νab(k) = ∞. In this paper, we present an O(κ|E|) algorithm for computing νab(i), i = 0, …, κ −1. The latter algorithm constructs a set of κ pairwise edge-disjoint schedule-conforming paths P0, …, Pκ −1 such that the finish time of Pi is νab(i), i = 0, 1, …, κ −1. (A path P = ae1u1e2 ··· Upp−1epb is schedule-conforming if the finish time of edge ei is no greater than the start time of the next edge ei + 1.) The existence of such paths when α(e) = β(e) = 0, for all e ϵ E, implies Menger's Theorem. In this paper, we also show that the obvious analogs of these results for either multiedge deletions or vertex deletions do not hold. In fact, we show that the problem of finding k schedule-conforming paths such that no two paths pass through the same vertex (multiedge) is NP-complete, even for k = 2. © 1996 John Wiley & Sons, Inc.

Consider a multigraph G on n vertices whose edges are linearly ordered. The vertices of G may represent people and the edges two-way communication between pairs of people. A vertex $\upsilon $ is k-failure-safe in communicating with a vertex w if there is a path of ascending edges from $\upsilon $ to w even when any k edges of G are deleted. In this paper, we show that the minimum size $\mu ( n,k )$ of G such that one vertex communicates k-failure-safe with every other vertex is given by $\mu ( n,k ) = \lceil ( ( k + 2 )/2 ) ( n - 1 ) \rceil $ for $k\leqq n - 2$ and $\mu ( n,k ) = \lceil ( ( k + 1 )/2 )n \rceil $ for $k\geqq n - 2$. We also show that for $k\geqq 1$ the minimum size $\tau ( n,k )$ of G such that every vertex communicates k-failure-safe with every other vertex satisfies $\mu ( n,k ) + n - 2 \lceil \sqrt{n} \rceil \leqq \tau ( n,k )\leqq \lfloor ( k + 3/ 2 ) ( n - 1 ) \rfloor $. The problem of finding $\tau ( n,k )$ for $k = 0$ is the well-known telephone problem.

Part 1: Introduction to Algorithms 1. Introduction to Preliminaries 2. Design and Analysis Fundamentals 3. Mathematical Tools for Algorithm Analysis 4. Trees and Applications to Algorithms 5. More on Sorting Algorithms 6. Probability and Average Complexity of Algorithms Part 2: Major Design Strategies 7. The Greedy Method 8. Divide-and-Conquer 9. Dynamic Programming 10. Backtracking and Branch-and-Bound Part 3: Graph and Network Algorithms 11. Graphs and Digraphs 12. Minimum Spanning Tree and Shortest-Path Algorithms 13. Graph Connectivity and Fault-Tolerance of Networks 14. Matching and Network Flow Algorithms Part 4: Parallel and Distributed Algorithms 15. Introduction to Parallel Algorithms and Architectures 16. Parallel Design Strategies 17. Internet Algorithms 18. Distributed Computation Algorithms 19. Distributed Network Algorithms Part 5: Special Topics 20. String Matching and Document Processing 21. Balanced Search Trees 22. The Fast Fourier Transform 23. Heuristic Search Strategies: A*-Search and Game Trees 24. Probabilistic and Randomized Algorithms 25. Lower-Bound Theory 26. NP-Complete Problems 27. Approximation Algorithms Appendices A: Mathematical Notation and Background B: Linear Data Structures C: Interpolating Asympotic Behavior D: Random Walks in Digraphs E: Elementary Probability Theory F: Examples of Message-Passing Interface Code G: Pseudocode Conventions

Let G be a connected multigraph and let $( A, + ,0 )$ be any Abelian group. For k an integer, let $A ( k )$ denote the subgroup of A given by $A ( k ) = \{ a \in A | ka = 0 \}$. A bicycle over A is a cycle over A that is also a cocycle. The set $B ( A )$ of bicycles over A determines a group. In this paper we show that the spanning tree number t of G has a unique factorization $t = t_1 t_2 \cdots t_m $ such that $t_i $ is a multiple of $t_{i + 1} ,i = 1,2, \cdots ,m - 1$ and such that for every Abelian group A the group $B ( A )$ of bicycles over A is isomorphic to $A ( t_1 ) \times A ( t_2 ) \times \cdots \times A ( t_m )$. Using this result we obtain a number of results on the spanning tree number including two formulae for the spanning tree number.