Name
Abstract | ||
|---|---|---|
Given a graph G we consider the problem of preprocessing it so that given two vertices x,y and a set X of vertices, we can efficiently report the shortest path (or just its length) between x,y that avoids X. We attach labels to vertices in such a way that this length can be determined from the labels of x,y and the vertices X. For a graph with n vertices of tree-width or clique-width k, we construct labels of size O(k 2log 2 n). The constructions extend to directed graphs. The problem is motivated by routing in networks in case of failures or of routing policies which forbid certain paths. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00224-009-9211-9 | Theory Comput. Syst. |
Keywords | Field | DocType |
Algorithms,Labelling schemes,Compact routing,Clique-width | Graph center,Discrete mathematics,Combinatorics,Path (graph theory),Induced path,Chordal graph,Distance,Cycle graph,Independent set,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
47 | 2 | 1432-4350 |
Citations | PageRank | References |
5 | 0.40 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Courcelle | 1 | 3418 | 388.00 |
| Andrew Twigg | 2 | 62 | 6.31 |