Name
Abstract | ||
|---|---|---|
Link reversal is the basis of several well-known routing algorithms [1,2,3]. In these algorithms, logical directions are imposed on the communication links and a node that becomes a sink reverses some of its incident links to allow the (re)construction of paths to the destination. In the Full Reversal (FR) algorithm [1], a sink reverses all its incident links. In other schemes, a sink reverses only some of its incident links; a notable example is the Partial Reversal (PR) algorithm [1]. Prior work [4] has introduced a generalization, called LR, of link-reversal routing, including FR and PR. In this paper, we show that every execution of LR on any link-labeled input graph corresponds, in a precise sense, to an execution of FR on a transformed graph. Thus, all the link reversal schemes captured by LR can be reduced to FR, indicating that "partial is full." The correspondence preserves the work and time complexities. As a result, we can, for the first time, obtain the exact time complexity for LR, and by specialization for PR. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22212-2_11 | SIROCCO |
Keywords | Field | DocType |
link reversal scheme,link-labeled input graph corresponds,incident link,exact time complexity,full reversal,link-reversal routing,link reversal,partial reversal,time complexity,communication link | Discrete mathematics,Graph,Algorithm,Directed graph,Time complexity,Mathematics,Sink (computing),Routing algorithm | Conference |
Volume | ISSN | Citations |
6796 | 0302-9743 | 6 |
PageRank | References | Authors |
0.50 | 18 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernadette Charron-bost | 1 | 785 | 67.22 |
| Matthias Függer | 2 | 167 | 21.14 |
| Jennifer L. Welch | 3 | 1806 | 257.97 |
| Josef Widder | 4 | 229 | 23.99 |