Studies on the design of algorithms for reliable networks and its application

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

In modern society, we have many networks such as traffic networks and communication networks. It is required that such networks have some fault-tolerance. The concepts of graph connectivity are known as one measure of network fault-tolerance. In this research, we proposed several efficient algorithms for connectivity augmentation problems and source location problems, which are well-known as graph problems concerning connectivity. Also, we generalized these results, which may contribute to the analysis of other problems.