A Greedy Algorithm for Minimum Cut into Bounded Sets Problem
Bildiriler > Tam Metin Bildiri
Yazarlar: Onur Ugurlu, Vahıd AKRAM, Deniz Tursel Eliiyi
2021 17th International Conference on Network and Service Management (CNSM), , , Uluslararası, Tam Metin Bildiri, ss 422-426
DOI: 10.23919/cnsm52442.2021.9615583
Özet
Finding critical links and weak points is an important task in almost all types of networks. Minimum cuts provide useful information about the critical links. However, finding a minimum cut of a network may provide insufficient or misleading information on critical links since the number of disconnected nodes in the residual network is not taken into account in this problem. In this work, we study the minimum cut into bounded sets problem, which limits the number of nodes in portioned sets. Finding the minimum cut into bounded sets can provide useful information on important critical links in a different network, whose failure has a hard and unacceptable effect. The minimum cut into bounded sets problem is an open NP-Complete problem. We propose a greedy algorithm for this problem with$O\left(c \times n^{2}\right)$time complexity and present computational results on random networks. To the best of our knowledge, the proposed algorithm is the first heuristic for the minimum cut into bounded sets problem.