摘要
Multipath Routing plays an important role in communication networks. Multiple disjoint paths can increase the effective bandwidth between pairs of vertices, avoid congestion in a network and reduce the probability of dropped packets. In this paper, we built mathematical models for arc-disjoint paths problem and vertex-disjoint paths problem respectively, and then proposed polynomial algorithms for finding the shortest pair of arc and vertex-disjoint paths, both with the time complexity of O(m). Furthermore, we extend these algorithms to find any k disjoint paths in time O(km), whose sum-weight is minimized.
| 源语言 | 英语 |
|---|---|
| 主期刊名 | 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 |
| 页 | 539-544 |
| 页数 | 6 |
| DOI | |
| 出版状态 | 已出版 - 2009 |
| 已对外发布 | 是 |
| 活动 | 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 - Chengdu, 中国 期限: 12 12月 2009 → 14 12月 2009 |
出版系列
| 姓名 | 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 |
|---|
会议
| 会议 | 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 |
|---|---|
| 国家/地区 | 中国 |
| 市 | Chengdu |
| 时期 | 12/12/09 → 14/12/09 |
指纹
探究 'Finding arc and vertex-disjoint paths in networks' 的科研主题。它们共同构成独一无二的指纹。引用此
Xie, Z., Chen, Z., Leng, H., & Zhang, J. (2009). Finding arc and vertex-disjoint paths in networks. 在 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 (页码 539-544). 文章 5380407 (8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009). https://doi.org/10.1109/DASC.2009.75