|
An $O(|V||E|^{2})$ Time Algorithm to Diagnose the Solvability of Single Rate $n$-Pair Networks with Common Bottleneck Links
|
| |
|
|
|
چکیده: (170 مشاهده) |
| Cai et al.(2013) and Cai and Han (2014) presented the polynomial time algorithms for two-pair and three-pair networks with common bottleneck links, respectively. Also, Chen and HaiBin(2012) proposed a non-polynomial time algorithms for $n$-pair networks with common bottleneck links, where $n$ is an arbitrary integer. This paper presents a new sufficient and necessary condition to determine the solvability of single rate $n$-pair networks with common bottleneck links, which concludes a polynomial time algorithm for $n$-pair networks with common bottleneck links, where $n$ is an arbitrary integer. Our algorithm runs in $O(|V||E|^{2})$ time, where $|V|$ and $|E|$ are the number of nodes and links, respectively. |
|
| |
|
|
متن کامل [PDF 533 kb]
(92 دریافت)
|
نوع مطالعه: پژوهشی |
موضوع مقاله:
Discrete Optimization
دریافت: 1403/8/21 | پذیرش: 1404/3/12 | انتشار: 1404/3/12
|
|
|
|
|
|
|
| ارسال نظر درباره این مقاله |
|
|
|
