Academic Journal
Empirical study on sufficient numbers of minimum cuts in strongly connected directed random graphs
| العنوان: | Empirical study on sufficient numbers of minimum cuts in strongly connected directed random graphs |
|---|---|
| المؤلفون: | Chang, Eric, Cheng, C. K., Gupta, Anushka, Hsu, Po‐Ya, Moffitt, Amanda, Ren, Alissa, Tsaur, Irene, Wang, Samuel |
| المساهمون: | NSF |
| المصدر: | Networks ; volume 76, issue 1, page 106-121 ; ISSN 0028-3045 1097-0037 |
| بيانات النشر: | Wiley |
| سنة النشر: | 2020 |
| المجموعة: | Wiley Online Library (Open Access Articles via Crossref) |
| الوصف: | We focus on the all‐pairs minimum cut (APMC) problem, a graph partitioning problem whose solution requires finding the minimum cut for every pair of nodes in a given graph. While it is solved for undirected graphs, a solution for APMC in directed graphs still requires an O ( n 2 ) brute force approach. We show that the empirical number of distinct minimum cuts in randomly generated strongly connected directed graphs is proportional to n rather than the theoretical value of n 2 , suggesting the possibility of an algorithm which finds all minimum cuts in less than O ( n 2 ) time. We also provide an example of the strict upper bound on the number of cuts in graphs with three nodes. We model the distributions with the Generalized extreme value (GEV) distribution and enable the possibility of using a GEV distribution to predict the probability of achieving a certain number of minimum cuts, given the number of nodes and edges. Finally, we contribute to the notion of symmetric cuts by showing that there can be O ( n 2 ) symmetric cuts in graphs when node replication is allowed. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| DOI: | 10.1002/net.21943 |
| الاتاحة: | http://dx.doi.org/10.1002/net.21943 https://api.wiley.com/onlinelibrary/tdm/v1/articles/10.1002%2Fnet.21943 https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.21943 https://onlinelibrary.wiley.com/doi/full-xml/10.1002/net.21943 https://onlinelibrary.wiley.com/doi/am-pdf/10.1002/net.21943 |
| Rights: | http://onlinelibrary.wiley.com/termsAndConditions#am ; http://onlinelibrary.wiley.com/termsAndConditions#vor |
| رقم الانضمام: | edsbas.F65AF1CE |
| قاعدة البيانات: | BASE |
| DOI: | 10.1002/net.21943 |
|---|