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   Vol.E80-A   No.1   pp.183-193
Publication Date: 1997/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Reliability and Fault Analysis
embedding,  binary,  trees,  proper pathwidth,  bandwidth,  grids,  ,  

Full Text: PDF>>
Buy this Article

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.