d-Separated Paths in Hypercubes and Star Graphs

概要

論文の詳細を見る
In this paper, we consider a generalized node disjoint paths problem : d-separated paths problem. In a graph G, given two distinct nodes s and t, two paths P and Q, connecting sand t, are d-separated if d_<G-{s,t}>(u,v)≥d for any u ∈ P - {s,t} and v ∈ Q - {s,t}, where d_<G-{s,t}>(u,v) is the distance between u and v in the reduced graph G - {s,t}. d-separated paths problem is to find as many d-separated paths between s and t as possible. In this paper, we give the following results on d-separated paths problems on n-dimensional hypercubes H_n and star graphs G_n. Given s and t in H_n, there are at least (n-2) 2-separated paths between s and t. (n-2) is the maximum number of 2-separated paths between sand t for d(s,t)≥4. Moreover, (n-2) 2-separated paths of length at most min{d(s,t)+2, n+1} for d(s,t) < n and of length n for d(s,t) = n between s and t can be constructed in O(n^2) optimal time. For d≥3, d-separated paths in H_n do not exist. Given s and t in G_n, there are exactly (n-1) d-separated paths between s and t for 1≤d≤3. (n-1) 3-separated paths of length at most min{d(s,t)+4, d(G_n)+ 2} between s and t can be constructed in O(n^2) optimal time, where d(G_n)=⌊3(n-1)/2⌋. For d≥5, d-separated paths in G_n do not exist.
一般社団法人情報処理学会の論文
1995-11-17