Finding Four Independent Trees

DOI10.1137/S0097539703436734zbMath1101.05064OpenAlexW2015485656MaRDI QIDQ5470724

Xingxing Yu, Orlando Lee, Sean Curran

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

algorithm independent spanning trees Connectivity numbering chain decomposition

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) Connectivity (05C40)

Related Items

Construction independent spanning trees on locally twisted cubes in parallel, Constructing edge-disjoint spanning trees in twisted cubes, A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, An algorithm to construct independent spanning trees on parity cubes, A comment on ``Independent spanning trees in crossed cubes, Completely independent spanning trees in line graphs, Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs, Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Spanning trees: A survey, Independent spanning trees on twisted cubes, A fast parallel algorithm for constructing independent spanning trees on parity cubes, Construction of optimal independent spanning trees on folded hypercubes, A parallel algorithm for constructing independent spanning trees in twisted cubes, Completely independent spanning trees in torus networks, Parallel construction of multiple independent spanning trees on highly scalable datacenter networks, Constructing independent spanning trees for locally twisted cubes, Independent spanning trees on even networks, Structural properties of subdivided-line graphs, CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2), Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Independent spanning trees on folded hyper-stars, 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 improved algorithm to construct edge-independent spanning trees in augmented cubes, Mondshein Sequences (a.k.a. (2,1)-Orders), Constructing Node-Independent Spanning Trees in Augmented Cubes, Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks, Four Edge-Independent Spanning Trees, Independent spanning trees in crossed cubes