Though one whole week of instructions is still to go before the end-sem exams begin, two out of three of my teaching days next week are holidays. (I am not complaining!) On Monday, which is the only day of my teaching schedule left in this semester, I plan to conduct a tutorial. So teaching is indeed over for this semester. As research now comes to the foreground, I thought I should mention something interesting I read.
Recently I saw a Lemma by Eberfeld, Jakoby and Tantau which proves that given any graph of tree-width at most k, a O(log n) depth tree-decomposition of it witnessing width slightly more than k, say 4k, can be found in polytime (in fact in logspace). It is a nice result! I expect it to find some applications. It probably should be thought of as a depth reduction result. If the input graph is a tree of depth D, it is easy to find a depth D (which could be O(n)), width 1 tree-decomposition for it. What this Lemma says is that, we can find a depth O(log n) and width 8 decomposition for it. It may be interesting to give an alternate/simple proof for trees.
Recently I saw a Lemma by Eberfeld, Jakoby and Tantau which proves that given any graph of tree-width at most k, a O(log n) depth tree-decomposition of it witnessing width slightly more than k, say 4k, can be found in polytime (in fact in logspace). It is a nice result! I expect it to find some applications. It probably should be thought of as a depth reduction result. If the input graph is a tree of depth D, it is easy to find a depth D (which could be O(n)), width 1 tree-decomposition for it. What this Lemma says is that, we can find a depth O(log n) and width 8 decomposition for it. It may be interesting to give an alternate/simple proof for trees.
Comments