Advertisement
Published in:
2007 | OriginalPaper | Chapter
Compact Forbidden-Set Routing
Authors : Bruno Courcelle, Andrew Twigg
Published in: STACS 2007
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study labelling schemes for
X
-constrained path problems. Given a graph (
V
,
E
) and
$X\subseteq 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\subseteq 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
(
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.