Two conditions for reducing the maximal length of node-disjoint paths in hypercubes

DOI10.1016/j.tcs.2011.11.009zbMath1232.68016OpenAlexW2037249467MaRDI QIDQ764341

Cheng-Nan Lai

Publication date: 13 March 2012

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

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

zbMATH Keywords

hypercubematchingoptimization problemnode-disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07)

Related Items

Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs, On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups

Cites Work

• Unnamed Item
• Unnamed Item
• Many-to-many disjoint paths in faulty hypercubes
• Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults
• Longest fault-free paths in hypercubes with vertex faults
• Generalized diameters and Rabin numbers of networks
• Combinatorial properties of generalized hypercube graphs
• From Hall's matching theorem to optimal routing on hypercubes
• An efficient algorithm for the \(k\)-pairwise disjoint paths problem in hypercubes
• Node-disjoint paths in hierarchical hypercube networks
• Strong Rabin numbers of folded hypercubes
• w -Rabin numbers and strong w -Rabin numbers of folded hypercubes
• On Disjoint Shortest Paths Routing on the Hypercube
• Efficient algorithms for finding maximum matching in graphs
• Efficient dispersal of information for security, load balancing, and fault tolerance
• On the Rabin number problem