Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids

Satoshi TAYU; Shuichi UENO

Copy

Satoshi TAYU, Shuichi UENO, "Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 1, pp. 183-193, January 1997, doi: .
Abstract: It has been known that an N-vertex binary tree can be embedded into the path and grid with dilation O(N/logN) and O((N/logN)), respectively. This paper shows that an N-vertex binary tree with proper pathwidth at most k can be embedded into the path grid with dilation O(N/N^1/k) and O((N/N^1/2k)), respectively.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_1_183/_p

Copy

@ARTICLE{e80-a_1_183,
author={Satoshi TAYU, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids},
year={1997},
volume={E80-A},
number={1},
pages={183-193},
abstract={It has been known that an N-vertex binary tree can be embedded into the path and grid with dilation O(N/logN) and O((N/logN)), respectively. This paper shows that an N-vertex binary tree with proper pathwidth at most k can be embedded into the path grid with dilation O(N/N^1/k) and O((N/N^1/2k)), respectively.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 183
EP - 193
AU - Satoshi TAYU
AU - Shuichi UENO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1997
AB - It has been known that an N-vertex binary tree can be embedded into the path and grid with dilation O(N/logN) and O((N/logN)), respectively. This paper shows that an N-vertex binary tree with proper pathwidth at most k can be embedded into the path grid with dilation O(N/N^1/k) and O((N/N^1/2k)), respectively.
ER -