A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks

DOI10.1007/978-3-030-93176-6_22zbMath1498.68205OpenAlexW4205818074MaRDI QIDQ2151377

Ralf Klasing, Shih-Shun Kao, Sun-Yuan Hsieh, Ling-Ju Hung

Publication date: 1 July 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-93176-6_22

zbMATH Keywords

interconnection networksindependent spanning treesbubble-sort networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• Unnamed Item
• Unnamed Item
• A comment on ``Independent spanning trees in crossed cubes
• Two counterexamples on completely independent spanning trees
• A parallel algorithm for constructing independent spanning trees in twisted cubes
• Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes
• Independent spanning trees on twisted cubes
• A fast parallel algorithm for constructing independent spanning trees on parity cubes
• On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)
• The multi-tree approach to reliability in distributed networks
• Three completely independent spanning trees of crossed cubes with application to secure-protection routing
• The fault tolerance of \(( n , k )\)-bubble-sort networks
• Broadcasting secure messages via optimal independent spanning trees in folded hypercubes
• A two-stages tree-searching algorithm for finding three completely independent spanning trees
• Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks
• Construction independent spanning trees on locally twisted cubes in parallel
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Three tree-paths
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• A group-theoretic model for symmetric interconnection networks
• CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2)
• Independent Spanning Trees on Multidimensional Torus Networks
• Finding Four Independent Trees