Long paths in hypercubes with a quadratic number of faults

DOI10.1016/j.ins.2009.06.029zbMath1193.68051OpenAlexW2076524741MaRDI 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

hypercubelong pathlinear-time algorithmfaulty vertex

Mathematics Subject Classification ID

Applications of graph theory (05C90) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Rounds in combinatorial search, Edge-fault-tolerant diameter and bipanconnectivity of hypercubes, 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, 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, Conditional edge-fault Hamiltonicity of augmented cubes, Pancyclicity and bipancyclicity of conditional faulty folded hypercubes, The panpositionable panconnectedness of augmented cubes, Paired many-to-many disjoint path covers of hypercubes with faulty edges

Cites Work

• 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
• On Hamiltonian circuits and spanning trees of hypercubes
• Edge Multiplicity and Other Trace Functions
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices