Bandwidth of trees of diameter at most 4

详细信息	查看全文 | 推荐本文 |

• 作者：Mark Bilinski ^{mark.bilinski@gmail.com} ; Kwang Ju Choi ; Deborah Chun ; Guoli Ding ; Stan Dziobiak ; Rodrigo Farnham ; Perry Iverson ; Shirley Leu ; Lisa Warshauer Lowrance
• 关键词：Bandwidth ; Tree ; Polynomial time algorithm
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 July, 2012
• 卷：312
• 期：12-13
• 页码：1947-1951
• 文件大小：215 K

摘要

For a graph , let be a one-to-one function. The bandwidth of is the maximum of over . The bandwidth of , denoted , is the minimum bandwidth over all embeddings , . In this paper, we show that the bandwidth computation problem for trees of diameter at most 4 can be solved in polynomial time. This naturally complements the result computing the bandwidth for 2-caterpillars.