[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

B. Charron-Bost, M Függer, L. Welch, J. Widder:
"Partial is Full";
Vortrag: Structural Information and Communication Complexity, Gdansk; 26.06.2011 - 29.06.2011; in: "Structural Information and Communication Complexity", Springer Berlin / Heidelberg, (2011), ISBN: 978-3-642-22211-5; S. 113 - 124.



Kurzfassung englisch:
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.

Schlagworte:
Computer Science


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-22212-2_11


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.