A Greedy Algorithm for Minimum Cut into Bounded Sets Problem
Küçük Resim Yok
Tarih
2021
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
IEEE
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Ö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(c x n(2)) 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.
Açıklama
17th International Conference on Network and Service Management (CNSM) - Smart Management for Future Networks and Services -- OCT 25-29, 2021 -- ELECTR NETWORK
Anahtar Kelimeler
Network Connectivity, Minimum Cut, Critical Edges, Heuristics, Greedy Algorithms
