An edge-scheduled network N is a multigraph G = (V, E), where each edge e E E has been assigned two real weights: a start time a(e) and a finish time p(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 E 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 uab(k) is the earliest time t such that N is k-failure ab-invulnerable for the time period [O. t] [where vab(k) = 00 if no such t exists]. Let K denote the smallest k such that uab(k) = 00. In this paper, we present an O ( K I E l ) algorithm for computing uab(i), i = 0, . . . , K -1. The latter algorithm constructs a set of K pairwise edge-disjoint schedule-conforming paths Po, . . . , P,-l such that the finish time of PI is u&(i), i = 0, 1, . . . , K -1. (A path P = aelul e2 ---up-e@ is schedule-conforming if the finish time of edge el is no greater than the start time of the next edge e,+l .) The existence of such paths when a(e) = p(e) = 0, for all e 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. 0 7996 John Wiley & Sons, Inc.