2008 | OriginalPaper | Buchkapitel
Hamiltonicity of Matching Composition Networks with Conditional Edge Faults
verfasst von : Sun-Yuan Hsieh, Chia-Wei Lee
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we sketch structure characterization of a class of networks, called Matching Composition Networks (MCNs), to establish necessary conditions for determining the conditional fault hamiltonicity. We then apply our result to
n
-dimensional restricted hypercube-like networks, including
n
-dimensional crossed cubes, and
n
-dimensional locally twisted cubes, to show that there exists a fault-free Hamiltonian cycle if there are at most 2
n
− 5 faulty edges in which each node is incident to at least two fault-free edges. We also demonstrate that our result is worst-case optimal with respect to the number of faulty edges tolerated.