Topological properties of the class of hypercube-like graphs = 유사 하이퍼큐브 그래프 부류의 위상적 성질

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 366
  • Download : 0
In parallel computing, processors are connected into various interconnection networks. A number of network topologies have been suggested by several researchers. Among these topologies, the hypercube network is one of the most popular topologies due to many of its attractive properties. However, the hypercube is not best possible for its resources. Variations of the hypercube network have been discovered which further improve some of its properties. But due to a lack of the unified model, results on one network are hard to apply to other variants. We have chosen a class of hypercube variants, called the class of hypercube-like graphs. The class of hypercube-like graphs is proposed for the first time by Vaidya et al. The class retains many attractive properties of hypercube and contains most important hypercube variants. In this thesis, we introduce the class of HL-graphs and present the graph-theoretic properties of the class. We present two oblivious routing algorithms for the HL-graphs. The dimension reducing algorithm is a natural extension of the e-cube routing algorithm. The dimension detouring algorithm runs with look-ahead information. Both algorithms find a routing path at most n steps for an n-dimensional HL-graph. And we also present a deadlock-free wormhole routing algorithm for the HL-graphs. We introduce a new interconnection network topology, called a randomly twisted cube. We prove that the average distance of a randomly twisted cube is O(n/log n), which is asymptotically optimal. Our experiments show that the randomly twisted cube works well. We also show that the fault diameter of the HL-graph is at most n+[log(n-1)]. And we show that HL-graphs are hamiltonian. This result gives a positive answer to Vaidya``s conjecture. All HL-graphs are hamiltonian-connected or hamiltonian-laceable. And we show that HL-graphs are bipancyclic. We also show that HL-graphs retain hamiltonian properties when some edges or vertices are faulty.
Advisors
Chwa, Kyung-Yongresearcher좌경룡researcher
Description
한국과학기술원 : 전산학전공,
Publisher
한국과학기술원
Issue Date
2004
Identifier
237663/325007  / 000955143
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학전공, 2004.2, [ vi, 49 p. ]

Keywords

ROUTING; TWISTED CUBE; GRAPH THEORY; INTERCONNECTION NETWORKS; HAMILTONICITY; 해밀톤 성질; 라우팅; 꼬인 큐브; 그래프 이론; 상호연결망

URI
http://hdl.handle.net/10203/32860
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=237663&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0