Design of algorithms for problems of fault-tolerance of networks

点击翻译按钮获取中文摘要

In this study, we considered problems of domination in graphs, and the problem of completely independent spanning trees in graphs. It is known that these problems have been related to the problems of fault-tolerance in networks.First we considered the problems of domination in graphs, and we obtained some polynomial-time algorithms for problems of twin domination in round digraphs and local-tournaments which are well known classes of digraphs.Second, we considered the problem of completely independent spanning trees. This problem is a model of fault-tolerant routing in networks. We obtain some new sufficient condition of the existence of completely independent spanning trees in graphs.