Finding Four Independent Trees

DOI10.1137/S0097539703436734MaRDI QIDQ5470724zbMATH OpenOpenAlexFDO

Authors Sean Curran, Orlando Lee, Xingxing Yu

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539703436734

zbMATH Keywords

algorithmchain decompositionConnectivityindependent spanning treesnumbering

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1262807
• A linear-time algorithm to find four independent spanning trees in four connected planar graphs
• scientific article; zbMATH DE number 2079338
• Four edge-independent spanning trees
• scientific article; zbMATH DE number 1696542

Cited in

(40)

• 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\)
• An algorithm to construct independent spanning trees on parity cubes
• Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs
• Structural properties of subdivided-line graphs
• 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
• Broadcasting secure messages via optimal independent spanning trees in folded hypercubes
• An improved algorithm to construct edge-independent spanning trees in augmented cubes
• Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks
• Construction independent spanning trees on locally twisted cubes in parallel
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
• Constructing edge-disjoint spanning trees in twisted cubes
• scientific article; zbMATH DE number 1696542 (Why is no real title available?)
• Mondshein sequences (a.k.a. (2,1)-orders)
• Independent spanning trees on folded hyper-stars
• Four edge-independent spanning trees
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• A comment on ``Independent spanning trees in crossed cubes
• scientific article; zbMATH DE number 1262807 (Why is no real title available?)
• scientific article; zbMATH DE number 2079338 (Why is no real title available?)
• Completely independent spanning trees in torus networks
• Construction of optimal independent spanning trees on folded hypercubes
• Constructing node-independent spanning trees in augmented cubes
• A parallel algorithm for constructing independent spanning trees in twisted cubes
• CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2)
• A linear-time algorithm to find four independent spanning trees in four connected planar graphs
• Constructing independent spanning trees for locally twisted cubes
• Independent spanning trees on even networks
• Nonseparating Planar Chains in 4-Connected Graphs
• Chain Decompositions of 4-Connected Graphs
• Independent spanning trees in crossed cubes
• Completely independent spanning trees in line graphs
• Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes
• \((t, s)\)-completely independent spanning trees
• Spanning trees: A survey
• Independent spanning trees on twisted cubes
• Vertex-independent spanning trees in complete Josephus cubes
• A fast parallel algorithm for constructing independent spanning trees on parity cubes

This page was built for publication: Finding Four Independent Trees

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