Embed longest rings onto star graphs with vertex faults

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

研究成果: Conference contribution

15 引文 斯高帕斯(Scopus)

摘要

The star graph has been recognized as an attractive alternative to the hypercube. Let Fe and Fν be the sets of vertex faults and edge faults, respectively. Previously, Tseng et al. showed that an n-dimensional star graph can embed a ring of length n! if |Fe|≤n-3 (|Fν|=0), and a ring of length at least n!-4|Fν| if |Fν|≤n-3 (|Fe|=0). Since an n-dimensional star graph is regular of degree n-1 and is bipartite with two partite sets of equal size, our result achieves optimality in the worst case.

原文English
主出版物標題Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998
編輯Ten H. Lai
發行者Institute of Electrical and Electronics Engineers Inc.
頁面140-147
頁數8
ISBN(電子)0818686502
DOIs
出版狀態Published - 1998 一月 1
事件1998 International Conference on Parallel Processing, ICPP 1998 - Minneapolis, United States
持續時間: 1998 八月 101998 八月 14

出版系列

名字Proceedings of the International Conference on Parallel Processing
ISSN(列印)0190-3918

Other

Other1998 International Conference on Parallel Processing, ICPP 1998
國家United States
城市Minneapolis
期間98-08-1098-08-14

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Hardware and Architecture

指紋 深入研究「Embed longest rings onto star graphs with vertex faults」主題。共同形成了獨特的指紋。

引用此