An efficient algorithm to construct disjoint path covers of DCell networks

DOI10.1016/j.tcs.2015.09.022zbMath1331.68159OpenAlexW2172760123WikidataQ60402100 ScholiaQ60402100MaRDI QIDQ897875

Xi Wang, Cheng-Kuan Lin, Jianxi Fan, Xiao-Hua Jia

Publication date: 8 December 2015

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

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

zbMATH Keywords

Hamiltonian pathDCell networkdisjoint path coverdata center network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ Enhancing fault tolerance of balanced hypercube networks by the edge partition method ⋮ Super spanning connectivity on WK-recursive networks ⋮ Torus-like graphs and their paired many-to-many disjoint path covers ⋮ Constructing dual-CISTs of folded divide-and-swap cubes ⋮ The extra connectivity, extra conditional diagnosability and \(t/k\)-diagnosability of the data center network DCell ⋮ Paired 2-disjoint path covers of multi-dimensional torus networks with \(2n-3\) faulty edges ⋮ Constructing dual-CISTs of DCell data center networks ⋮ Reliability analysis of data center networks based on precise and imprecise diagnosis strategies ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ Unpaired Many-to-Many Disjoint Path Covers on Bipartite k-Ary n-Cube Networks with Faulty Elements ⋮ Fault-tolerant embedding of starlike trees into restricted hypercube-like graphs

Uses Software

• MapReduce
• Dryad

Cites Work

• Unnamed Item
• Two spanning disjoint paths with required length in generalized hypercubes
• Optimal broadcasting for locally twisted cubes
• One-to-one disjoint path covers on alternating group graphs
• Efficient unicast in bijective connection networks with the restricted faulty node set
• An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges
• One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes
• A quadratic algorithm for finding next-to-shortest paths in graphs
• On mapping processes to processors in distributed systems
• An oblivious shortest-path routing algorithm for fully connected cubic networks
• On structured digraphs and program testing
• The NP-completeness column: An ongoing gulde
• AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS
• Practical Deadlock-Free Fault-Tolerant Routing in Meshes Based on the Planar Network Fault Model
• One-to-one disjoint path covers on multi-dimensional tori

This page was built for publication: An efficient algorithm to construct disjoint path covers of DCell networks