Compact forbidden-set routing

We study labelling schemes for X-constrained path problems. Given a graph (V, E) and X subset of V, a path is X-constrained if all intermediate vertices avoid X. We study the problem of assigning labels J(x) to vertices so that given {J(x) : x G X} for any X C V, we can route on the shortest X-constrained path between x,y is an element of X. This problem is motivated by Internet routing, where the presence of routing policies means that shortest-path routing is not appropriate. For graphs of tree width k, we give a routing scheme using routing tables of size O(k(2) log(2) n). We introduce m-clique width, generalizing clique width, to show that graphs of m-clique width k also have a routing scheme using size O(k(2) log(2) n) tables.