MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTE'k-Chordal Graph: from Cops and Robber to Compact Routing via Treewidth
par Bi Li
| Date : | 06/03/12 | | Time : | 10:30 | | Location : | Lagrange gris |
Â' We present a quadratic algorithm that, given a graph G and k â'‰'¥ 3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each bag of which contains a dominating path with at most k â'ˆ' 1 vertices. As an application, for any n-node graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(log n) bits and achieving an additive stretch of O(k log â'ˆ'†).
Page des séminaires
| 
