|
A Faster Algorithm to Diagnose the Solvability of a Three-Pair Network with Common Bottleneck Links
|
| |
|
|
|
چکیده: (6 مشاهده) |
| A three-pair network consists of a directed acyclic graph with two sets $S={s_1,s_2,s_3}$ and $T={t_1,t_2,t_3}$ such that each $s_{i}in S$ generates a message $X_{i}$ and each $t_{i}in T$ wants to get the message $X_{i}$. This paper presents an $O(|E|^2)$ time algorithm to diagnose the solvability or unsolvability of three-pair networks with common bottleneck links, where $|E|$ is the number of links. The algorithm is a region decomposition method, which improves upon the previous polynomial time of $O(|E|^3)$ due to cite{CH}. |
|
| |
|
|
متن کامل [PDF 2553 kb]
(8 دریافت)
|
نوع مطالعه: پژوهشی |
موضوع مقاله:
Discrete Optimization
دریافت: 1404/10/17 | پذیرش: 1405/4/25 | انتشار: 1405/4/25
|
|
|
|
|
|
|
| ارسال نظر درباره این مقاله |
|
|
|
