Finding arc and vertex-disjoint paths in networks

Zheng Xie; Zhi Chen; Hongze Leng; Jun Zhang

doi:10.1109/DASC.2009.75

Finding arc and vertex-disjoint paths in networks

Zheng Xie^*, Zhi Chen, Hongze Leng, Jun Zhang

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009
Pages	539-544
Number of pages	6
DOIs	https://doi.org/10.1109/DASC.2009.75
Publication status	Published - 2009
Externally published	Yes
Event	8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 - Chengdu, China Duration: 12 Dec 2009 → 14 Dec 2009

Publication series

Name	8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009

Conference

Conference	8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009
Country/Territory	China
City	Chengdu
Period	12/12/09 → 14/12/09

Keywords

Arc-disjoint
Minimized
Multipath
Vertex-disjoint
Weight

Access to Document

10.1109/DASC.2009.75

Cite this

@inproceedings{d117c9bc818744ccbab206c9d7b899a4,

title = "Finding arc and vertex-disjoint paths in networks",

abstract = "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.",

keywords = "Arc-disjoint, Minimized, Multipath, Vertex-disjoint, Weight",

author = "Zheng Xie and Zhi Chen and Hongze Leng and Jun Zhang",

year = "2009",

doi = "10.1109/DASC.2009.75",

language = "English",

isbn = "9780769539294",

series = "8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009",

pages = "539--544",

booktitle = "8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009",

note = "8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009 ; Conference date: 12-12-2009 Through 14-12-2009",

}

Xie, Z, Chen, Z, Leng, H & Zhang, J 2009, Finding arc and vertex-disjoint paths in networks. in 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009., 5380407, 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009, pp. 539-544, 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009, Chengdu, China, 12/12/09. https://doi.org/10.1109/DASC.2009.75

Finding arc and vertex-disjoint paths in networks. / Xie, Zheng; Chen, Zhi; Leng, Hongze et al.
8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009. 2009. p. 539-544 5380407 (8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Finding arc and vertex-disjoint paths in networks

AU - Xie, Zheng

AU - Chen, Zhi

AU - Leng, Hongze

AU - Zhang, Jun

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Arc-disjoint

KW - Minimized

KW - Multipath

KW - Vertex-disjoint

KW - Weight

UR - http://www.scopus.com/inward/record.url?scp=77950585091&partnerID=8YFLogxK

U2 - 10.1109/DASC.2009.75

DO - 10.1109/DASC.2009.75

M3 - Conference contribution

AN - SCOPUS:77950585091

SN - 9780769539294

T3 - 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009

SP - 539

EP - 544

BT - 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009

T2 - 8th IEEE International Symposium on Dependable, Autonomic and Secure Computing, DASC 2009

Y2 - 12 December 2009 through 14 December 2009

ER -

Finding arc and vertex-disjoint paths in networks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this