Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices

DOI10.1137/060678476zbMath1187.05056MaRDI 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

hypercube; fault tolerance; Hamiltonian cycle; NP-complete; Hamiltonian path; path partition; faulty vertex

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68M07: Mathematical problems of computer architecture

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M15: Reliability, testing and fault tolerance of networks and computer systems

05C45: Eulerian and Hamiltonian graphs

Related Items

General-demand disjoint path covers in a graph with faulty elements, Hamiltonicity of hypercubes with faulty vertices, Algorithms for finding disjoint path covers in unit interval graphs, Paired many-to-many disjoint path covers in restricted hypercube-like graphs, Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Paired many-to-many disjoint path covers in faulty hypercubes, Gray codes with bounded weights, The 2-path-bipanconnectivity of hypercubes, Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs, Hamiltonian laceability of hypercubes without isometric subgraphs, Generalized Gray codes with prescribed ends, Many-to-many disjoint paths in hypercubes with faulty vertices, Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements, Computational complexity of long paths and cycles in faulty hypercubes, 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, Paired many-to-many disjoint path covers of hypercubes with faulty edges, Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes, Paired 2-disjoint path covers of multidimensional torus networks with faulty edges, Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes, Ore-type degree conditions for disjoint path covers in simple graphs, Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs, Path partitions of 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, Edge-fault-tolerant diameter and bipanconnectivity of hypercubes, One-to-one disjoint path covers in digraphs, Torus-like graphs and their paired many-to-many disjoint path covers, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Disjoint path covers with path length constraints in restricted hypercube-like graphs, Disjoint path covers joining prescribed source and sink sets in interval graphs, Many-to-many two-disjoint path covers in restricted hypercube-like graphs, Single-source three-disjoint path covers in cubes of connected graphs, 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, Hamiltonian fault-tolerance of hypercubes