For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids
Satoshi TAYU Shuichi UENO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/01/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Reliability and Fault Analysis
embedding, binary, trees, proper pathwidth, bandwidth, grids, ,
Full Text: PDF>>
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/N1/k) and O((N/N1/2k)), respectively.