Long paths in hypercubes with a quadratic number of faults

DOI10.1016/j.ins.2009.06.029zbMath1193.68051MaRDI QIDQ730952

Václav Koubek, Tomáš Dvořák

Publication date: 1 October 2009

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2009.06.029

zbMATH Keywords

hypercube; long path; linear-time algorithm; faulty vertex

Mathematics Subject Classification ID

05C90: Applications of graph theory

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

Rounds in combinatorial search, The 2-path-bipanconnectivity of hypercubes, Many-to-many disjoint paths in hypercubes with faulty vertices, Computational complexity of long paths and cycles in faulty hypercubes, Paired many-to-many disjoint path covers of hypercubes with faulty edges, Conditional edge-fault Hamiltonicity of augmented cubes, Pancyclicity and bipancyclicity of conditional faulty folded hypercubes, The panpositionable panconnectedness of augmented cubes, Long cycles in hypercubes with optimal number of faulty vertices, On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube, Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph, Efficient Connectivity Testing of Hypercubic Networks with Faults

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long paths and cycles in hypercubes with faulty vertices
• Longest fault-free paths in hypercubes with vertex faults
• Graphs, networks and algorithms
• Long paths in hypercubes with conditional node-faults
• Data compression and Gray-code sorting
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Edge Multiplicity and Other Trace Functions
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices