𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Congestion-free embedding of 2(n−k) spanning trees in an arrangement graph

✍ Scribed by Yuh-Shyan Chen; Tong-Ying Juang; Ying-Ying Shen

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
912 KB
Volume
47
Category
Article
ISSN
1383-7621

No coin nor oath required. For personal study only.

✦ Synopsis

The arrangement graph A nYk is not only a generalization of star graph (n À k 1), but also more ¯exible. In this investigation, we elucidate the problem of embedding of multiple spanning trees in an arrangement graph with the objective of congestion-free. This result is to report how to exploit 2n À k edge disjoint spanning trees in an arrangement graph, where each congestion-free spanning tree's height is 2k À 1. Our scheme is based on a subgraphpartitioning scheme. First, we construct 2n À k base spanning trees in every A nÀk2Y2 . Then, we recursively construct 2n À k spanning trees from every A nÀk2Y2 up to A nYk by a bottom-up approach. This is a near-optimal result since all of possible edges in the base subarrangement A nÀk2Y2 are fully utilized.

📜 SIMILAR VOLUMES

Embedding k(n−k) edge-disjoint spanning
Embedding k(n−k) edge-disjoint spanning trees in arrangement graphs
✍ Chin-Tsai Lin 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 278 KB

The arrangement graphs are a class of generalized star graphs. In this paper we construct a graph that consists of the maximum number of directed edge-disjoint spanning trees in an arrangement graph. The paths that connect the common root node to any given node through different spanning trees are n

Congestion-free, dilation-2 embedding of
Congestion-free, dilation-2 embedding of complete binary trees into star graphs
✍ Tseng, Yu-Chee; Chen, Yuh-Shyan; Juang, Tong-Ying; Chang, Chiou-Jyu 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB 👁 2 views

Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilati

The existence of a 2-factor in K1, n-fre
The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity
✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.

A partial m=(2k+1)-cycle system of order
A partial m=(2k+1)-cycle system of order n can be embedded in an m-cycle system of order (2n+1)m
✍ C.C. Lindner; C.A. Rodger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 566 KB

A generalization of Cruse's Theorem on embedding partial idempotent commutative latin squares is developed and used to show that a partial m = (2k + I)-cycle system of order n can be embedded in an m-cycle system of order tm for every odd t 2 (2n + 1).