焦げたパンケーキグラフにおける内素な経路問題

全文

(1)情報処理学会第67回全国大会. 1N-2 †. †. † †. 1. 1. 2. n n. d. ri (1 ≤ i ≤ n) n=2 Bn. s. 2. 2. n≥3. s = ( s1 , s 2 ,..., s n ) d = (1, 2, ..., n) i (1 ≤ | i | ≤ n − 1). 1. Bn ti =. (| i | +1, | i | +2, ..., n, | 1 |, | 2 |, ..., | i | −1, i ). 1 n 1, 2, ..., n bi ∈ {− 1,+1} (1 ≤ i ≤ n ). u = (a1 × b1 , a 2 × b2 ,..., a n × bn ) 1, 2, ..., n 2 n 1,2,..., n u = (u1 , u 2 ,..., u n ). sn = n. n. rn s → s ( n ) → s ( n, j ) → s ( n, j ,n ) →* t −1 →* d j | s n − j +1 |= 1. n. ri (1 ≤ i ≤ n − 1) Bn −1 n s d n −1. u (i ) u (i ) = (− u i ,−u i −1 ,...,−u1 , u i +1 , u i + 2 ,..., u n ). s1 ≠ ± n ri (2 ≤ i ≤ n − 1). ui n. 3. Bn 1, 2, ..., n. n 1. {u. (i ). n! × 2 u = (u1 , u 2 ,..., u n ). Bn 2n k Bn −1 k. s → s (i ) → s (i ,n ) →*. t si → * d. }. r1 s1 > 0. k n −1. s (1,n ,1,n ). s → s (1) → s (1,n ) →* t s1 →* d s → s (1) → s (1,n ) → s (1,n ,1) → →* t s1 →* d. rn. Bn−1 Bn 2. s n ≠ ±1, n. s → s (i ) → s (i ,1) → s (i ,1,n ) →*. t si → * d. n. |1 ≤ i ≤ n. Bn. si < 0. →*. s1 > 0 t sn → * d. 2. An algorithm for node-disjoint paths in burnt pancake graphs †Naoki Sawada, Yasuto Suzuki, Keiichi Kaneko †Faculty of Technology, Tokyo Univ. of Agri. and Tech.. s1 = n. 1−249. s → s ( n ) → s ( n,1) → s ( n,1,n ) →* s → s ( n ) → * t sn → * d. | s1 | = n j =1. s n ≠ ±1 j=n.

(2) rj. s→s →s s → s ( n ) →* d. j =1. (1). rj. (n). → d. 100,000 1 d = (1, 2, ..., n) 2. v. d. n. n. *. v1 ri (1 ≤ i ≤ n, i ≠ j , si ≠ v1 ) ri (1 ≤ i ≤ n) rk ( s k = v1 ). 50 1, 2. s. 2.5. O(n ). s → s ( k ) → s ( k ,n ) → s ( k ,n ,1) → s ( k ,n ,1,n ) →* t s. 2. n O(n 2.07 ). n. → d *. s1 ≠ ± n 2. Bn. | sn | = 1 s t sn. u. 2. O(n 2.5 ) O(n 2.07 ). s u1. r|u1|. s → * t sn → * d ri (1 ≤ i ≤ n, i ≠ u1 ) ri (1 ≤ i ≤ n) s1 = n. | s1 | = n j =1 2. | sn | = 1 j=n s t sn. u. s u1. rj. 1. rj r|u1| (| v1 | ≠ 1, n). s → * t sn → * d rn+1− j ( s1 ≠ | u1 |). s → s ( n ) → s ( n,1) → s ( n,1,n ) →* t s →* d s → s (1) → s (1,n ) j =1. n. →s. (1,n ,1). → s (1,n ,1,n ) →* t s →* d n. ri (2 ≤ i ≤ n − 1, i ≠ | u1 |, si ≠ v1 ) ri (1 ≤ i ≤ n) rk ( s k = v1 , k ≠ | u1 |) rk. 2 [ 1 ] W. H. Gates et al. : Bounds for sorting by prefix reversal, Discrete Math., Vol. 27, pp. 47-57, 1979. [ 2 ] K. Kaneko: An algorithm for node-to-set disjoint paths problem in burnt pancake graphs, IEICE Trans. Info. & Sys., Vol. E86-D, pp. 2588-2594, 2003.. 1−250.

(3)