Integrated Research on Connectivity of Graphs and its Applications

本项目的主题是促进图的连通性的理论刻画和设计实用算法及其应用的研究。结果总结如下(1)和(2).(1)给出了分析(计算给定图的连通性)、提取(从图中提取具有指定连通度的子图)和构造(通过添加最少数目的边来构造给定连通度的图)的理论特征和算法.(2)得到了用于实际应用的各种算法，如在线的、并行的或分布式的.

The subject of this project is to promote research on theoretical characterization and designing practical algorithms on connectivity of graphs and its applications. The results are summarized in the following (1) and (2).(1) Theoretical characterizations and algorithms for analysis (computing connectivity of a given graph), extraction (extracting a subgraph with prescribed connectivity from a graph), and construction (constructing a graph of given connectivity by adding a minimum number of edges) are given.(2) Various algorithms, such as online, parallel or distributed ones, for practical use in applications are obtained.