Minimum Congestion Embedding of Complete Binary Trees into Tori

Akira MATSUBAYASHI; Ryo TAKASU

Minimum Congestion Embedding of Complete Binary Trees into Tori

Akira MATSUBAYASHI, Ryo TAKASU

Full Text Views

0

Cite this

Summary :

We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2ⁿ-1-vertex complete binary tree can be embedded in a (2^n/2+1)(2^n/2+1)-grid and a 2^n/2 2^n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2ⁿ-1-vertex complete binary tree is embeddable in a 2^n/2 2^n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2ⁿ-1-vertex complete binary tree can be embedded with unit congestion in a 2^n/2 2^n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2ⁿ-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.9 pp.1804-1808

Publication Date: 2000/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Akira MATSUBAYASHI, Ryo TAKASU, "Minimum Congestion Embedding of Complete Binary Trees into Tori" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 9, pp. 1804-1808, September 2000, doi: .
Abstract: We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2ⁿ-1-vertex complete binary tree can be embedded in a (2^n/2+1)(2^n/2+1)-grid and a 2^n/2 2^n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2ⁿ-1-vertex complete binary tree is embeddable in a 2^n/2 2^n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2ⁿ-1-vertex complete binary tree can be embedded with unit congestion in a 2^n/2 2^n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2ⁿ-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_9_1804/_p

Copy

@ARTICLE{e83-a_9_1804,
author={Akira MATSUBAYASHI, Ryo TAKASU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Minimum Congestion Embedding of Complete Binary Trees into Tori},
year={2000},
volume={E83-A},
number={9},
pages={1804-1808},
abstract={We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2ⁿ-1-vertex complete binary tree can be embedded in a (2^n/2+1)(2^n/2+1)-grid and a 2^n/2 2^n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2ⁿ-1-vertex complete binary tree is embeddable in a 2^n/2 2^n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2ⁿ-1-vertex complete binary tree can be embedded with unit congestion in a 2^n/2 2^n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2ⁿ-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - Minimum Congestion Embedding of Complete Binary Trees into Tori
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1804
EP - 1808
AU - Akira MATSUBAYASHI
AU - Ryo TAKASU
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2000
AB - We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2ⁿ-1-vertex complete binary tree can be embedded in a (2^n/2+1)(2^n/2+1)-grid and a 2^n/2 2^n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2ⁿ-1-vertex complete binary tree is embeddable in a 2^n/2 2^n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2ⁿ-1-vertex complete binary tree can be embedded with unit congestion in a 2^n/2 2^n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2ⁿ-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.
ER -