Long paths in hypercubes with a quadratic number of faults

DOI10.1016/J.INS.2009.06.029MaRDI QIDQ730952zbMATH OpenOpenAlexFDO

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

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

hypercubelinear-time algorithmfaulty vertexlong path

Mathematics Subject Classification ID

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

Recommendations

• Long paths and cycles in hypercubes with faulty vertices
• Long paths and cycles in faulty hypercubes: existence, optimality, complexity
• Long paths in hypercubes with conditional node-faults
• Longest fault-free paths in hypercubes with vertex faults
• Embedded paths and cycles in faulty hypercubes

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• Data compression and Gray-code sorting
• Edge Multiplicity and Other Trace Functions
• Graphs, networks and algorithms
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Long paths and cycles in hypercubes with faulty vertices
• Long paths in hypercubes with conditional node-faults
• Longest fault-free paths in hypercubes with vertex faults
• On Hamiltonian circuits and spanning trees of hypercubes
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices

Cited in

(17)

• Paired many-to-many disjoint path covers of hypercubes with faulty edges
• Conditional edge-fault Hamiltonicity of augmented cubes
• Long cycles in hypercubes with optimal number of faulty vertices
• Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph
• Long paths in hypercubes with conditional node-faults
• Path embedding in faulty hypercubes
• Pancyclicity and bipancyclicity of conditional faulty folded hypercubes
• Longest fault-free paths in hypercubes with vertex faults
• Computational complexity of long paths and cycles in faulty hypercubes
• Rounds in combinatorial search
• Efficient connectivity testing of hypercubic networks with faults
• On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
• The 2-path-bipanconnectivity of hypercubes
• The panpositionable panconnectedness of augmented cubes
• Many-to-many disjoint paths in hypercubes with faulty vertices
• Long paths and cycles in hypercubes with faulty vertices
• Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

This page was built for publication: Long paths in hypercubes with a quadratic number of faults

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730952)