標題: | Christmas tree: A versatile 1-fault-tolerant design for token rings |
作者: | Hung, CN Hsu, LH Sung, TY 資訊工程學系 Department of Computer Science |
關鍵字: | diameter;Hamiltonian;1-Hamiltonian;Hamiltonian-connected;fault-tolerant;token rings |
公開日期: | 29-十月-1999 |
摘要: | The token ring topology is required in token passing approach used in distributed operating systems. Fault tolerance is also required in the designs of distributed systems. Note that 1-fault-tolerant design for token rings is equivalent to design of 1-Hamiltonian graphs. This paper introduces a new family of graphs called Christmas tree, denoted by CT(s). The graph CT(s) is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes in CT(s) is 3.2(s) - 2. Its diameter is 1 if s = 1, 3 if s = 2, and 2s if s greater than or equal to 3. (C) 1999 Elsevier Science B.V. All rights reserved. |
URI: | http://hdl.handle.net/11536/31025 |
ISSN: | 0020-0190 |
期刊: | INFORMATION PROCESSING LETTERS |
Volume: | 72 |
Issue: | 1-2 |
起始頁: | 55 |
結束頁: | 63 |
顯示於類別: | 期刊論文 |