A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance
| Autor: | Yong-Zen Huang, Lih-Hsing Hsu, Y-Chuang Chen, Jimmy J. M. Tan |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Computer science Hardware_PERFORMANCEANDRELIABILITY Theoretical Computer Science Combinatorics Computer Science::Hardware Architecture Indifference graph symbols.namesake TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Superintegrable Hamiltonian system Mathematics::Symplectic Geometry Computer Science::Operating Systems Computer Science::Distributed Parallel and Cluster Computing Connectivity Hamiltonian path problem Adiabatic quantum computation Hamiltonian path Graph Vertex (geometry) Hardware and Architecture symbols Hypercube Software MathematicsofComputing_DISCRETEMATHEMATICS Information Systems |
| Zdroj: | The Journal of Supercomputing. 54:229-238 |
| ISSN: | 1573-0484 0920-8542 |
| DOI: | 10.1007/s11227-009-0316-3 |
| Popis: | Processor (vertex) faults and link (edge) faults may happen when a network is used, and it is meaningful to consider networks (graphs) with faulty processors and/or links. A k-regular Hamiltonian and Hamiltonian connected graph G is optimal fault-tolerant Hamiltonian and Hamiltonian connected if G remains Hamiltonian after removing at most k?2 vertices and/or edges and remains Hamiltonian connected after removing at most k?3 vertices and/or edges. In this paper, we investigate in constructing optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected graphs. Therefore, some of the generalized hypercubes, twisted-cubes, crossed-cubes, and Mobius cubes are optimal fault-tolerant Hamiltonian and optimal fault-tolerant Hamiltonian connected. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink