A fast parallel algorithm for constructing independent spanning trees on parity cubes

DOI10.1016/j.amc.2015.06.081zbMath1410.05195MaRDI QIDQ668143

Yue-Li Wang, Jou-Ming Chang, Jinn-Shyong Yang, Yu-Huei Chang

Publication date: 18 March 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2015.06.081

zbMATH Keywords

parallel algorithms; interconnection networks; independent spanning trees; parity cubes

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A parallel algorithm for constructing independent spanning trees in twisted cubes, Edge-independent spanning trees in augmented cubes, A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks, Modelling simultaneous broadcasting by level-disjoint partitions

Cites Work

• Embedding meshes into twisted-cubes
• The multi-tree approach to reliability in distributed networks
• The twisted-cube connected networks
• Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security
• An algorithm to construct independent spanning trees on parity cubes
• Broadcasting secure messages via optimal independent spanning trees in folded hypercubes
• Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
• Three tree-paths
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Finding Four Independent Trees
• Independent spanning trees in crossed cubes