کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650825 | 1342504 | 2008 | 22 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Tree-decompositions with bags of small diameter Tree-decompositions with bags of small diameter](/preview/png/4650825.png)
This paper deals with the length of a Robertson–Seymour's tree-decomposition. The tree-length of a graph is the largest distance between two vertices of a bag of a tree-decomposition, minimized over all tree-decompositions of the graph. The study of this invariant may be interesting in its own right because the class of bounded tree-length graphs includes (but is not reduced to) bounded chordality graphs (like interval graphs, permutation graphs, AT-free graphs, etc.). For instance, we show that the tree-length of any outerplanar graph is ⌈k/3⌉⌈k/3⌉, where k is the chordality of the graph, and we compute the tree-length of meshes.More fundamentally we show that any algorithm computing a tree-decomposition approximating the tree-width (or the tree-length) of an n -vertex graph by a factor αα or less does not give an αα-approximation of the tree-length (resp. the tree-width) unless if α=Ω(n1/5)α=Ω(n1/5). We complete these results presenting several polynomial time constant approximate algorithms for the tree-length.The introduction of this parameter is motivated by the design of compact distance labeling, compact routing tables with near-optimal route length, and by the construction of sparse additive spanners.
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2008–2029