A polynomial-time algorithm for message routing in hierarchical communication-networks

The hierarchical communication network considered in this paper is a two-level network, which is used for communicating messages between some pairs of nodes of the network. The first level network consists of capacitated arcs between communicating pairs of nodes and the second level network consists of a spanning tree. Assuming that the flow requirements increase over time at a constant rate for each communicating pair, the decision problem is to determine, for each communicating pair of nodes, the time when the communication will break down due to insufficient capacity of arcs in the network. In this paper, we develop an O(n² + nw) time algorithm to solve this problem, where n denotes the number of nodes in the network and w denotes the number of communicating node pairs.