Reconnectable network with limited resources
Tóm tắt
The reachability of a strongly connected network may be destroyed after link damage. Since many networks are directed or equivalent directed, connected by directed links with the potential for reversal. Therefore the reachability can be restored by reversing the direction of links. [1] has studied this matter under unlimited resources (transmitter and receiver) condition. In this paper the reconnectability of a network with limited number of receivers and transmitters is discussed. Also a linear time algorithm is given to find a reconnected reversal for limited receivers and transmitters.
Tài liệu tham khảo
W. Shi and R. Juels, Connected reorientation of mixed multigraphs.Network,19 (1989), 235–246.
H. Robbins, A theorem on graphs with an application to a problem of traffic control.American Math. Monthly,4G (1939), 281–283.
F. Boesch and R. Tindell, Robbin's Theorem for mixed multigraphs.American Math. Monthly,87 (1980), 716–719.