본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.32 no.8, 2005년, pp.426 - 431   피인용횟수: 2

이중 루프 네트워크의 다대다 서로소인 경로 커버
Many-to-Many Disjoint Path Covers in Double Loop Networks

박정흠   (카톨릭대학교 컴퓨터정보공학부UU0013933  );
  • 초록

    그래프 G의 다대다 k-서로소인 경로 커버(k-DPC)는 k개의 서로 다른 소스 정점과 싱크 정점 쌍을 연결하며 그래프에 있는 모든 정점을 지나는 k개의 서로소인 경로 집합을 말한다. 이 논문에서는 이중 루프 네트워크 G(mn;1,m)에서 다대다 2-DPC를 고찰하여, 이분 그래프가 아닌 모든 G(mn;l,m), $m{\geq}3$ 은 임의의 두 소스-싱크 쌍을 연결하는 다대다 2-DPC가 존재하고 이분 그래프인 G(mn;1,m)은 두 흰색-검정 소스-싱크 쌍이거나 혹은 검정-검정, 흰색-흰색 쌍을 연결하는 2-DPC가 존재함을 보인다. G(mn;1,m)은 m이 홀수이고 n이 짝수일 경우에만 이분 그래프이다.


    A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. In this paper, we investigate many-to-many 2-DPC in a double loop network G(mn;1,m), and show that every nonbipartite G(mn;1,m), $m{\geq}3$ , has 2-DPC joining any two source-sink pairs of vertices and that every bipartite G(mn;1,m) has 2-DPC joining any two source-sink pairs of black-white vertices and joining any Pairs of black-black and white-white vertices. G(mn;l,m) is bipartite if and only if n is odd and n is even.


  • 주제어

    서로소인 경로 커버 .   이중 루프 네트워크 .   강한 해밀톤 성질 .   상호 연결망 .   circulant 그래프.  

  • 참고문헌 (18)

    1. J.-H. Park, 'One-to-one disjoint path covers in recursive circulants,' Journal of KISS, 30(12), pp. 691-698, 2003     
    2. C.-H. Tsai, J.J.M. Tan, and L.-H. Hsu, 'The super-connected property of recursive circulant graphs,' Inform. Proc. Lett., 91(6), pp. 293-298, 2004 
    3. C.-H. Chang, C.-K. Lin, H.-M. Huang, and L.-H. Hsu, 'The super laceability of the hypercubes,' Inform. Proc. Lett., 92(1), pp. 15-21, 2004 
    4. J.-H. Park, 'One-to-many disjoint path covers in a graph with faulty elements,' in Proc. of the International Computing and Combinatorics Conference COCOON 2004, pp. 392-401, Aug. 2004 
    5. J.-H. Park, H.-C. Kim, and H.-S. Lim, 'Manyto-many disjoint path covers in a graph with faulty elements,' in Proc. of the International Symposium on Algorithms and Computation ISAAC 2004, pp. 742-753, Dec. 2004 
    6. J.-H. Park, H.-C. Kim, and H.-S. Lim, 'Manyto-many disjoint path covers in hypercube-like interconnection networks with faulty elements,' IEEE Trans. Parallel and Distributed Systems, 2005 (to appear) 
    7. C.-y. Chou, D.J. Guan, and K.-l. Wang, 'A dynamic fault-tolerant message routing algorithm for double-loop networks,' Inform. Proc. Lett., 70(6), pp. 259-264, 1999 
    8. D.J. Guan, 'An optimal message routing algorithm for double-loop networks,' Inform. Proc. Lett., 65(5), pp. 255-260, 1998 
    9. T.-Y. Sung, C.-Y. Lin, Y.-C. Chuang, and L.-H. Hsu, 'Fault tolerant token ring embedding in double loop networks,' Inform. Proc. Lett., 66, pp. 201-207, 1998 
    10. J.-H. Park, H.-C. Kim, and H.-S. Lim, 'Faulthamiltonicity of hypercube-like interconnection networks,' in Proc. of the IEEE International Parallel & Distributed Processing Symposium IPDPS 2005, Apr. 2005 
    11. A. Sengupta, 'On ring embedding in hypercubes with faulty nodes and links,' Inform. Proc. Lett., 68, pp. 207-214, 1998 
    12. Y.-C. Tseng, S.-H. Chang, and J.-P. Sheu, 'Fault-tolerant ring embedding in a star graph with both link and node failures,' IEEE Trans. Parallel and Distributed Systems, 8(12), pp. 1185-1195, Dec. 1997 
    13. J.-H. Park and H.-C. Kim, 'Fault hamiltonicity of double loop networks G(mn;1,m) with even m and n,' Journal of KISS, 27(10), pp. 868-879, 2000 
    14. C.-H. Tsai, J.J.M. Tan, Y.-C. Chuang, and L.-H. Hsu, 'Fault-free cycles and links in faulty recursive circulant graphs,' in Proc. of Workshop on Algorithms and Theory of Computation ISC2000, pp. 74-77, 2000 
    15. J.-H. Park, 'Fault-hamiltonicity of bipartite double loop networks,' Journal of KISS, 31(1), pp. 19-26, 2004     
    16. C.C. Chen and N.F. Quimpo, 'On strongly hamiltonian abelian group graphs,' in. Australian Conference on Combinatorial Mathematics (Lecture Notes in Mathematics #884), pp. 23-34, 1980 
    17. H.-C. Kim and J.-H. Park, 'Fault hamiltonicity of two-dimensional torus networks,' in Proc. of Workshop on Algorithms and Computation WAAC'00, Tokyo, Japan, pp. 110-117, 2000 
    18. J.-H. Park and H.-C. Kim, 'Fault-hamiltonicity of product graph of path and cycle,' in Proc. of International Computing and Combinatorics Conference COCOON2003 (LNCS #2697), MT, USA, pp. 319-328, 2003 
  • 이 논문을 인용한 문헌 (2)

    1. Park, Jung-Heum 2006. "Unpaired Many-to-Many Disjoint Path Covers in Hypercube-Like Interconnection Networks" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 33(10): 789~796     
    2. Park, Jung-Heum 2007. "Conditions for Disjoint Path Coverability in Proper Interval Graphs" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 34(10): 539~554     

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기