Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

DOI10.1016/j.ipl.2010.03.012zbMath1229.68057OpenAlexW2040681998MaRDI QIDQ656593

Jia-Cian Lin, Jinn-Shyong Yang, Chiun-Chieh Hsu, Jou-Ming Chang

Publication date: 18 January 2012

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

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

zbMATH Keywords

interconnection networksindependent spanning treesedge-disjoint spanning treeslocally twisted cubesfault-tolerant broadcasting

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Construction independent spanning trees on locally twisted cubes in parallel ⋮ Locally exchanged twisted cubes: connectivity and super connectivity ⋮ A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks ⋮ Embedding mutually edge-disjoint cycles into locally twisted cubes ⋮ An algorithm to construct independent spanning trees on parity cubes ⋮ The generalized 4-connectivity of locally twisted cubes ⋮ Optimal broadcasting for locally twisted cubes ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Embedding three edge-disjoint Hamiltonian cycles into locally twisted cubes ⋮ Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes ⋮ Independent spanning trees on twisted cubes ⋮ Construction of optimal independent spanning trees on folded hypercubes ⋮ Edge-independent spanning trees in augmented cubes ⋮ Fault-tolerant edge-pancyclicity of locally twisted cubes ⋮ Independent spanning trees on even networks ⋮ Broadcasting secure messages via optimal independent spanning trees in folded hypercubes ⋮ Independent spanning trees in crossed cubes ⋮ A two-stages tree-searching algorithm for finding three completely independent spanning trees ⋮ Changing the diameter of the locally twisted cube ⋮ A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks

Cites Work

• Independent spanning trees of chordal rings
• Node-pancyclicity and edge-pancyclicity of hypercube variants
• Constructing edge-disjoint spanning trees in locally twisted 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
• Independent trees in planar graphs
• Embedding \(k\)(\(n-k\)) edge-disjoint spanning trees in arrangement graphs.
• Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security
• Locally twisted cubes are 4-pancyclic.
• Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults
• Panconnectivity of locally twisted cubes
• A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM\(^{*}\) model
• Three tree-paths
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs
• Edge-disjoint spanning trees on the star network with applications to fault tolerance
• The locally twisted cubes
• CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2)
• Independent Spanning Trees on Multidimensional Torus Networks
• Optimum broadcasting and personalized communication in hypercubes
• Finding Four Independent Trees
• Independent spanning trees with small depths in iterated line digraphs