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
. This result generalizes to trees, planar graphs, and any family of graphs with treewidth
. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|