Node-to-Set Disjoint Paths with Optimal Length in Star Graphs

Qian-Ping GU; Shietung PENG

Node-to-Set Disjoint Paths with Optimal Length in Star Graphs

Qian-Ping GU, Shietung PENG

Full Text Views

0

Cite this

Summary :

In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t₁,...,t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s t_i, 1 i k. We give an O(n²) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(G_n) + 1 for n 4,6 and at most d(G_n) + 2 for n = 4,6, where d(G_n) = 3(n-1)/2 is the diameter of G_n. d(G_n) + 1 and d(G_n) + 2 are also the lower bounds on the length of the paths for the above problem in G_n for n 4,6 and n = 4,6, respectively.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.4 pp.425-433

Publication Date: 1997/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Supercomputing)

Category

Cite this

Copy

Qian-Ping GU, Shietung PENG, "Node-to-Set Disjoint Paths with Optimal Length in Star Graphs" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 4, pp. 425-433, April 1997, doi: .
Abstract: In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t₁,...,t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s t_i, 1 i k. We give an O(n²) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(G_n) + 1 for n 4,6 and at most d(G_n) + 2 for n = 4,6, where d(G_n) = 3(n-1)/2 is the diameter of G_n. d(G_n) + 1 and d(G_n) + 2 are also the lower bounds on the length of the paths for the above problem in G_n for n 4,6 and n = 4,6, respectively.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_4_425/_p

Copy

@ARTICLE{e80-d_4_425,
author={Qian-Ping GU, Shietung PENG, },
journal={IEICE TRANSACTIONS on Information},
title={Node-to-Set Disjoint Paths with Optimal Length in Star Graphs},
year={1997},
volume={E80-D},
number={4},
pages={425-433},
abstract={In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t₁,...,t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s t_i, 1 i k. We give an O(n²) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(G_n) + 1 for n 4,6 and at most d(G_n) + 2 for n = 4,6, where d(G_n) = 3(n-1)/2 is the diameter of G_n. d(G_n) + 1 and d(G_n) + 2 are also the lower bounds on the length of the paths for the above problem in G_n for n 4,6 and n = 4,6, respectively.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Node-to-Set Disjoint Paths with Optimal Length in Star Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 425
EP - 433
AU - Qian-Ping GU
AU - Shietung PENG
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 1997
AB - In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t₁,...,t_k} of k nodes in a k-connected graph G, find k node-disjoint paths s t_i, 1 i k. We give an O(n²) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs G_n which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(G_n) + 1 for n 4,6 and at most d(G_n) + 2 for n = 4,6, where d(G_n) = 3(n-1)/2 is the diameter of G_n. d(G_n) + 1 and d(G_n) + 2 are also the lower bounds on the length of the paths for the above problem in G_n for n 4,6 and n = 4,6, respectively.
ER -