Computational complexity of long paths and cycles in faulty hypercubes

DOI10.1016/J.TCS.2010.07.001MaRDI QIDQ708231zbMATH OpenOpenAlexFDO

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

Publication date 11 October 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.07.001

zbMATH Keywords

hypercubeNP-hardfaulty vertexlong cyclelong path

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Network design and communication in computer systems (68M10)

Recommendations

• Long paths and cycles in faulty hypercubes: existence, optimality, complexity
• Long paths in hypercubes with a quadratic number of faults
• Long paths and cycles in hypercubes with faulty vertices
• Embedded paths and cycles in faulty hypercubes
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices

Cites work

• scientific article; zbMATH DE number 3874608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• Embedded paths and cycles in faulty hypercubes
• Fault-tolerant cycle embedding in the hypercube
• Hamiltonian Cycles with Prescribed Edges in Hypercubes
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Long paths and cycles in hypercubes with faulty vertices
• Long paths in hypercubes with a quadratic number of faults
• Long paths in hypercubes with conditional node-faults
• Longest fault-free paths in hypercubes with vertex faults
• On the Existence of Hamiltonian Circuits in Faulty Hypercubes
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices

Cited in

(9)

• Embedded paths and cycles in faulty hypercubes
• Long cycles in hypercubes with optimal number of faulty vertices
• Long paths and cycles in faulty hypercubes: existence, optimality, complexity
• Hamiltonian laceability in hypercubes with faulty edges
• Longest fault-free paths in hypercubes with vertex faults
• Gray codes with bounded weights
• Efficient connectivity testing of hypercubic networks with faults
• On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube
• Generalized Gray codes with prescribed ends

This page was built for publication: Computational complexity of long paths and cycles in faulty hypercubes

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