التفاصيل البيبلوغرافية
| العنوان: |
ON THE PARAMETERIZED COMPLEXITY OF COUNTING SMALL-SIZED MINIMUM (S, T)-CUTS. |
| المؤلفون: |
BERGÉ, PIERRE, BOUAZIZ, WASSIM, RIMMEL, ARPAD, TOMASIK, JOANNA |
| المصدر: |
SIAM Journal on Discrete Mathematics; 2023, Vol. 37 Issue 2, p964-996, 33p |
| مصطلحات موضوعية: |
COUNTING, UNDIRECTED graphs, ALGORITHMS |
| مستخلص: |
The counting of minimum edge (S, T)-cuts in undirected graphs, parameterized by the size p of these cuts, is FPT. The best performance in the literature is O* (2O(p²)). We treat a more general problem of counting minimum (S, T)-cuts composed of vertices instead of edges. We propose an FPT algorithm with running time O* (2O(p log p)). As it may be applied to the edge version as well, we improve the time complexity of the minimum edge (S, T)-cuts counting. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
