|
An $O(|V||E|^{2})$ Time Algorithm to Diagnose the Solvability of Single Rate $n$-Pair Networks with Common Bottleneck Links
|
Sepideh Ghazvineh   , Mehdi Ghiyasvand * |
| Bu-Ali Sina University , meghiyasvand@yahoo.com |
|
|
Abstract: (169 Views) |
| 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. |
|
| Keywords: Network coding, Single rate n-pair networks, Bottleneck links, Solvability. |
|
|
Full-Text [PDF 533 kb]
(92 Downloads)
|
Type of Study: Original |
Subject:
Discrete Optimization
Received: 2024/11/11 | Accepted: 2025/06/2 | Published: 2025/06/2
|
|
|
|
|
|
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
