An optimal greedy routing algorithm for triangulated polygons |
| |
Authors: | Omkar Kulkarni Huaming Zhang |
| |
Institution: | Computer Science Department, The University of Alabama in Huntsville, Huntsville, AL 35899, United States |
| |
Abstract: | In this paper, we prove that a triangulated polygon G admits a greedy embedding into an appropriate semi-metric space such that using an appropriate distance definition, for any two vertices u and w in G, a most virtual distance decreasing path is always a minimum-edge path between u and w. Therefore, our greedy routing algorithm is optimal. The greedy embedding of G can be obtained in linear time. To the best of our knowledge, this is the first optimal greedy routing algorithm for a nontrivial subcategory of graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|