Speaker:

Binglin Tao (Ph.D. student in University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• 21:20-22:20 (Time in Auckland)
• May 20, 2022 (Friday)

Venue:

B1-518B, Research Building 4

Abstract:

As networks and their inter-connectivity grow and become complex, failures in the networks impact society and industries more than ever. To address this limitation, we consider region-based connectivity to capture the local nature of failures under the geographical failure model, where failures may happen only on edges in a sub-network (region) and we want to shield some edges in regions to protect the connectivity. There may be several regions and in different regions the failures occur independently. Firstly, we establish the NP-hardness of the problem for l regions, answering a question proposed in previous papers. Secondly, we propose a polynomial-time algorithm for the special case of two regions based on the matroid techniques. Furthermore, we design an ILP-based algorithm to solve the problem for l regions. Experimental results on random and real networks show that our algorithms are much faster than previously known algorithms.