Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults

DOI10.1007/s00224-008-9108-zzbMath1187.68344OpenAlexW2017861455MaRDI QIDQ733731

Yu-Fen Weng, Sun-Yuan Hsieh

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9108-z

zbMATH Keywords

Hamiltonianhypercubesfault-tolerant embeddinggraph-theoretic interconnection networkspairwise independent Hamiltonian paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (16)

Hamiltonian decomposition of generalized recursive circulant graphs ⋮ Mutually independent Hamiltonian cycles of binary wrapped butterfly graphs ⋮ Paired many-to-many disjoint path covers in faulty hypercubes ⋮ Two spanning disjoint paths with required length in generalized hypercubes ⋮ Mutually independent bipanconnected property of hypercube ⋮ Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees ⋮ On the mutually independent Hamiltonian cycles in faulty hypercubes ⋮ Independent spanning trees on twisted cubes ⋮ Rooted level-disjoint partitions of Cartesian products ⋮ A Fault-Free Unicast Algorithm in the Generalized Hypercube with Restricted Faulty Vertices ⋮ Many-to-many disjoint paths in hypercubes with faulty vertices ⋮ Diameter variability of hypercubes ⋮ Edge-fault-tolerant strong Menger edge connectivity of bubble-sort star graphs ⋮ Modelling simultaneous broadcasting by level-disjoint partitions ⋮ Embedding multidimensional grids into optimal hypercubes ⋮ Two conditions for reducing the maximal length of node-disjoint paths in hypercubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embedding longest fault-free paths onto star graphs with more vertex faults
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Linear array and ring embeddings in conditional faulty hypercubes
• Fault-tolerant Hamiltonian laceability of hypercubes.
• Embedding Hamiltonian cycles into folded hypercubes with faulty links
• A dual-Hamiltonian-path-based multicasting strategy for wormhole-routed star graph interconnection networks.
• Generalized Hypercube and Hyperbus Structures for a Computer Network
• Embedding cube-connected cycles graphs into faulty hypercubes
• Hamiltonian-laceability of star graphs
• Longest fault-free paths in star graphs with vertex faults

This page was built for publication: Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults