TY - GEN
T1 - Partial is full
AU - Charron-Bost, Bernadette
AU - Függer, Matthias
AU - Welch, Jennifer L.
AU - Widder, Josef
PY - 2011/8/10
Y1 - 2011/8/10
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-642-22212-2_11
DO - 10.1007/978-3-642-22212-2_11
M3 - Conference contribution
AN - SCOPUS:79961146708
SN - 9783642222115
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 113
EP - 124
BT - Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Proceedings
T2 - 18th Colloquium on Structural Information and Communication Complexity, SIROCCO 2011
Y2 - 26 June 2011 through 29 June 2011
ER -