Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks

DOI10.1007/S10878-019-00430-0MaRDI QIDQ2331598zbMATH OpenOpenAlexWikidataFDO

Authors Shih-Shun Kao, Kung-Jui Pai, Sun-Yuan Hsieh, Ro-Yu Wu, Jou-Ming Chang

Publication date 29 October 2019

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-019-00430-0

zbMATH Keywords

amortized analysisbubble-sort networksindependent spanning treesinterconnection networksmultiple spanning trees protocol

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Constructing independent spanning trees on bubble-sort networks
• A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks
• Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs
• Independent spanning trees on even networks
• On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)

Cites work

• A group-theoretic model for symmetric interconnection networks
• A new class of interconnection networks based on the alternating group
• A parallel algorithm for constructing independent spanning trees in twisted cubes
• A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks
• Arrangement graphs: A class of generalized star graphs
• Broadcasting secure messages via optimal independent spanning trees in folded hypercubes
• Construction independent spanning trees on locally twisted cubes in parallel
• Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs
• Estimating the subsystem reliability of bubblesort networks
• Fault tolerance in bubble-sort graph networks
• Finding Four Independent Trees
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Hamiltonian laceability of bubble-sort graphs with edge faults
• Optimum broadcasting and personalized communication in hypercubes
• Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs
• Subnetwork preclusion for bubble-sort networks
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The 1-good-neighbour diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model
• The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM\(^\ast\) model
• The (n,k)-star graph: A generalized star graph
• The multi-tree approach to reliability in distributed networks
• Three tree-paths
• Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security

Cited in

(6)

• Constructing independent spanning trees on bubble-sort networks
• A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks
• The maximum number of spanning trees of a graph with given matching number
• Linear time algorithms for finding independent spanning trees on pyramid networks
• Edge-independent spanning trees in folded crossed cubes
• Approximate Itai-Zehavi conjecture for random graphs

This page was built for publication: Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331598)