Paper Info
Title
Compact forbidden-set routing
Abstract
We study labelling schemes for X-constrained path problems. Given a graph (V,E) and X ⊆ 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 ∈ X} for any X ⊆ V, we can route on the shortest X-constrained path between x, y ∈ 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(k2 log2 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(k2 log2 n) tables.
Year
DOI
Venue
2007
10.1007/978-3-540-70918-3_4
STACS
Keywords
Field
DocType
m-clique width k,shortest-path routing,compact forbidden-set routing,tree width k,internet routing,size o,routing table,clique width,k2 log2 n,routing scheme,m-clique width,algorithms
Discrete mathematics,Equal-cost multi-path routing,Combinatorics,Link-state routing protocol,Path vector protocol,Destination-Sequenced Distance Vector routing,Private Network-to-Network Interface,Treewidth,Routing table,Mathematics,K shortest path routing
Conference
Volume
ISSN
Citations 
4393
0302-9743
16
PageRank 
References 
Authors
0.71
24
2
Name
Order
Citations
PageRank
Bruno Courcelle13418388.00
Andrew Twigg2626.31