|
A Faster Algorithm to Diagnose the Solvability of a Three-Pair Network with Common Bottleneck Links
|
Sepideh Ghazvineh   , Mehdi Ghiyasvand * |
| Bu-Ali Sina University , mghiyasvand@basu.ac.ir |
|
|
Abstract: (16 Views) |
| 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}. |
|
| Keywords: Network coding, Region decomposition method, Three-pair networks. |
|
|
Full-Text [PDF 2553 kb]
(15 Downloads)
|
Type of Study: Original |
Subject:
Discrete Optimization
Received: 2026/01/7 | Accepted: 2026/07/16 | Published: 2026/07/16
|
|
|
|
|
|
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
