On k-greedy routing algorithms

详细信息    查看全文

• 作者：Huaming Zhang^a ; ^{hzhang@cs.uah.edu" class="auth_mail" title="E-mail the corresponding author} ; Xiang-Zhi Kong^b ; ^{xiangzhikong@jiangnan.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Greedy routing ; k-Greedy routing ; k-Greedy drawing ; Plane graphs
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：9-17
• 全文大小：374 K

文摘

Let G=(V,E)$G=(V,E)$ and G^′=(V^′,E^′)$G^{\prime }=(V^{\prime },E^{\prime })$ be two graphs. A k-inverse-adjacency-preserving mapping ρ from G   to a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$ is a one-to-many and onto mapping from V   to V^′$V^{\prime }$ satisfying the following: (1) Each vertex v∈V$v\in V$ in G   is mapped to a non-empty subset ρ(v)⊂V^′$\rho (v)\subset V^{\prime }$ in a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$, the cardinality of ρ(v)$\rho (v)$ is at most k  ; (2) if u≠v$u\ne v$, then ρ(u)∩ρ(v)=∅$\rho (u)\cap \rho (v)=\varnothing$; and (3) for any u^′∈ρ(u)$u^{\prime }\in \rho (u)$ and v^′∈ρ(v)$v^{\prime }\in \rho (v)$, if (u^′,v^′)∈E^′$(u^{\prime },v^{\prime })\in E^{\prime }$, then (u,v)∈E$(u,v)\in E$. A vertex u^′$u^{\prime }$ in 34a11cf369e6f702d45a8c075e2" title="Click to view the MathML source">ρ(u)$\rho (u)$ is called a virtual location for u.

Let ρ be a k-inverse-adjacency-preserving-mapping (k-IAPM for short) from G   to a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$. Let δ   be a greedy drawing of a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$ into a metric space M$\mathcal{M}$. Consider a message from u to be delivered to v in G. Using the k-IAPM ρ from G   to a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$, intuitively, one can treat the message to be routed as if it were from one virtual location u^′$u^{\prime }$ for u   to one virtual location v^′$v^{\prime }$ for v, except that all the virtual locations of a vertex u   were identified with each other (which can be thought as instantaneously synchronized mirror sites for a particular website, for example). Then a routing path P^′$P^{\prime }$ can be computed from u^′$u^{\prime }$ to v^′$v^{\prime }$ while identifying all virtual locations for any vertex in G. Since ρ   inversely preserves adjacency from a07feebea923e665a270153" title="Click to view the MathML source">G^′$G^{\prime }$ to G  , such a routing path P^′$P^{\prime }$ corresponds to exactly one routing path P in G, which connects u to v.

In this paper, we formalize the above intuition into a concept which we call k-greedy routing algorithm for a graph G with n vertices, where k refers to the maximum number of virtual locations any vertex of G can have. Using this concept, the result presented in [18] can be rephrased as a 3-greedy routing algorithm for 3-connected plane graphs, where the virtual coordinates used are from 1 to 2n−2$2n-2$. In this paper, we present a 2-greedy routing algorithm for 3-connected plane graphs, where each vertex uses at least one but at most two virtual locations numbered from 1 to 2n−1$2n-1$. For the special case of plane triangulations (in a plane triangulation, every face is a triangle, including the exterior face), the numbers used are further reduced to from 1 to $\lfloor \frac{5n+1}{3}\rfloor$. Hence, there are at least $\lceil \frac{n-1}{3}\rceil$ vertices that use only one virtual location.