Acyclic K-connnected subgraphs for distributed alternate routing in communication networks.

In a communications network with a history-independent distributed routing control for calls to a particular destination, performance is enhanced if there is sufficiently diverse alternate routing capability and if cycles are avoided while a path is created. Such a routing relies on the construction of an acyclic subgraph in which all except k nodes are k-connected to the destination node. A linear-time algorithm generates a subgraph with these properties if such a subgraph exists. These subgraphs have a simple characterization. Whenever the conditions of the characterization are satisfied, a linear-time algorithm constructs k node-disjoint paths from a particular source code to the destination.