Computational complexity of long paths and cycles in faulty hypercubes

DOI10.1016/J.TCS.2010.07.001zbMath1207.68038OpenAlexW2057341189MaRDI QIDQ708231

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

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-hardlong cyclelong pathfaulty vertex

Mathematics Subject Classification ID

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

Related Items (6)

Long cycles in hypercubes with optimal number of faulty vertices ⋮ Hamiltonian laceability in hypercubes with faulty edges ⋮ Gray codes with bounded weights ⋮ On the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty hypercube ⋮ Efficient Connectivity Testing of Hypercubic Networks with Faults ⋮ Generalized Gray codes with prescribed ends

Cites Work

• Fault-tolerant cycle embedding in the hypercube
• Long paths and cycles in hypercubes with faulty vertices
• Long paths in hypercubes with a quadratic number of faults
• Longest fault-free paths in hypercubes with vertex faults
• Long paths in hypercubes with conditional node-faults
• Hyper-Hamilton laceable and caterpillar-spannable product graphs
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• On the Existence of Hamiltonian Circuits in Faulty Hypercubes
• Hamiltonian Cycles with Prescribed Edges in Hypercubes
• Embedded paths and cycles in faulty hypercubes
• Unnamed Item
• Unnamed Item
• Unnamed Item

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