Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

DOI10.1016/J.IPL.2010.11.018MaRDI QIDQ1944080zbMATH OpenOpenAlexFDO

Authors Xiebin Chen

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.11.018

zbMATH Keywords

Cartesian productfault-tolerant broadcastinggeneralized base-b hypercubeindependent spanning treesparallel algorithms

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Independent spanning trees in crossed cubes
• A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks
• Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
• A fast parallel algorithm for constructing independent spanning trees on parity cubes
• Construction of optimal independent spanning trees on folded hypercubes

Cites work

• Constructing edge-disjoint spanning trees in locally twisted cubes
• Constructing edge-disjoint spanning trees in twisted cubes
• CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2)
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs
• Embedding \(k\)(\(n-k\)) edge-disjoint spanning trees in arrangement graphs.
• Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links
• Finding Four Independent Trees
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Graph theory
• Independent spanning trees of chordal rings
• Independent Spanning Trees on Multidimensional Torus Networks
• Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes
• Independent trees in planar graphs
• On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)
• Reliable broadcasting in product networks
• The multi-tree approach to reliability in distributed networks
• The pancyclicity and the Hamiltonian-connectivity of the generalized base-\(b\) hypercube
• Three tree-paths
• Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security

Cited in

(14)

• On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\)
• A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks
• Constructing independent spanning trees on bubble-sort networks
• A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks
• A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks
• Parallel construction of multiple independent spanning trees on highly scalable datacenter networks
• Linear time algorithms for finding independent spanning trees on pyramid networks
• Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks
• Construction independent spanning trees on locally twisted cubes in parallel
• Construction of optimal independent spanning trees on folded hypercubes
• A parallel algorithm for constructing independent spanning trees in twisted cubes
• Independent spanning trees of product graphs
• Vertex-independent spanning trees in complete Josephus cubes
• Approximate Itai-Zehavi conjecture for random graphs

This page was built for publication: Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

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