首页 | 本学科首页   官方微博 | 高级检索  
     


Approximating the Bandwidth of Caterpillars
Authors:Uriel Feige  Kunal Talwar
Affiliation:(1) Weizmann Institute, Rehovot, Israel;(2) Microsoft Research, Mountain View, CA, USA
Abstract:A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time $2^{\tilde{O}(\sqrt{n/\epsilon})}$ . This result generalizes to trees, planar graphs, and any family of graphs with treewidth $\tilde{O}(\sqrt{n})$ .
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号