Abstract

Given a graph with labels defined on edges and two terminals  and , the Label  Cut problem asks to find the minimum number of labels such that the removal of edges with these labels can disconnect  and . This problem arose from many areas such as system security and computer network. It is easy to see that this problem is a generalization of the classic minimum  cut problem. The Label  Cut problem is NP-hard and can be approximated within , where  is the number of vertices in the graph. However, the weighted version, in which weights are defined on labels and the goal of the problem is to find the minimum total weight of labels, is not known how to approximate within a factor expressed by . In this talk we introduce such an algorithm. The novelty of the algorithm is an approach to interpret the label weight as edge length and edge capacity in the meanwhile.

Time

2022-07-19  13:30 - 14:30   

Speaker

Peng Zhang,  Shandong University

Room

Tencent meeting ID: 853-8759-9058; PW: 123456