Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices

DOI10.1137/060678476zbMath1187.05056OpenAlexW2089724497MaRDI QIDQ3648508

Petr Gregor, Tomáš Dvořák

Publication date: 27 November 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060678476

zbMATH Keywords

hypercubefault toleranceHamiltonian cycleNP-completeHamiltonian pathpath partitionfaulty vertex

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Mathematical problems of computer architecture (68M07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reliability, testing and fault tolerance of networks and computer systems (68M15) Eulerian and Hamiltonian graphs (05C45)

Related Items (41)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Paired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ Edge-fault-tolerant diameter and bipanconnectivity of hypercubes ⋮ Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes ⋮ Paired many-to-many disjoint path covers in faulty hypercubes ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Paired 2-disjoint path covers of multidimensional torus networks with faulty edges ⋮ Hamiltonian fault-tolerance of hypercubes ⋮ Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes ⋮ Ore-type degree conditions for disjoint path covers in simple graphs ⋮ Paired 2-disjoint path covers of burnt pancake graphs with faulty elements ⋮ One-to-one disjoint path covers in digraphs ⋮ Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements ⋮ Gray codes with bounded weights ⋮ Many-to-many two-disjoint path covers in restricted hypercube-like graphs ⋮ Single-source three-disjoint path covers in cubes of connected graphs ⋮ Torus-like graphs and their paired many-to-many disjoint path covers ⋮ Paired many-to-many disjoint path covers of the hypercubes ⋮ Disjoint path covers in cubes of connected graphs ⋮ Efficient Connectivity Testing of Hypercubic Networks with Faults ⋮ The 2-path-bipanconnectivity of hypercubes ⋮ Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs ⋮ General-demand disjoint path covers in a graph with faulty elements ⋮ Hamiltonian laceability of hypercubes without isometric subgraphs ⋮ Generalized Gray codes with prescribed ends ⋮ Many-to-many disjoint paths in hypercubes with faulty vertices ⋮ Path partitions of hypercubes ⋮ Computational complexity of long paths and cycles in faulty hypercubes ⋮ A class of hierarchical graphs as topologies for interconnection networks ⋮ On generalized middle-level problem ⋮ Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs ⋮ Paired many-to-many disjoint path covers of hypertori ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ Long paths in hypercubes with a quadratic number of faults ⋮ Many-to-many disjoint paths in faulty hypercubes ⋮ Hamiltonicity of hypercubes with faulty vertices ⋮ Paired many-to-many disjoint path covers of hypercubes with faulty edges ⋮ Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes ⋮ Many-to-many two-disjoint path covers in cylindrical and toroidal grids

This page was built for publication: Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices