The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] star graphs(1hit)

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

    Qian-Ping GU  Shietung PENG  

     
    PAPER

      Vol:
    E80-D No:4
      Page(s):
    425-433

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