Embed longest rings onto star graphs with vertex faults

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 1998 International Conference on Parallel Processing, ICPP 1998
EditorsTen H. Lai
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages140-147
Number of pages8
ISBN (Electronic)0818686502
DOIs
Publication statusPublished - 1998 Jan 1
Event1998 International Conference on Parallel Processing, ICPP 1998 - Minneapolis, United States
Duration: 1998 Aug 101998 Aug 14

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

Other1998 International Conference on Parallel Processing, ICPP 1998
CountryUnited States
CityMinneapolis
Period98-08-1098-08-14

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Embed longest rings onto star graphs with vertex faults'. Together they form a unique fingerprint.

  • Cite this

    Hsieh, S. Y., Chen, G. H., & Ho, C. W. (1998). Embed longest rings onto star graphs with vertex faults. In T. H. Lai (Ed.), Proceedings - 1998 International Conference on Parallel Processing, ICPP 1998 (pp. 140-147). (Proceedings of the International Conference on Parallel Processing). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPP.1998.708473