In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is c...In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.展开更多
Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algori...Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.展开更多
A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2...A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.展开更多
For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which ...For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.展开更多
Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky gra...Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky graphical images transfer. Therefore, the policies of assigning traffic to various service classes and providing service as per the service level agreement of the user with the network provider came into existence. Multi-protocol Label Switching is the backbone of fast switching technology that helps the network service providers to implement these policies. It provides Quality of service oriented reserved paths from the source to the destination for the user’s traffic. Selection of these paths is a cumbersome task, especially when the traffic forecast is totally unknown. Furthermore, nodes and link failures in the Internet worsen the situation. This paper addresses the issue of selecting Label Switched Paths (LSPs) for various traffic demands in the network so that the resultant network has the characteristics like high failure resistance, low LSP demand blocking probability, low impact from the node or link failure, load balancing and low over-all resource utilization. By extensive simulations, the proposed cost function has been compared with the various cost functions mentioned in the literature and it was found to score over them in major aspects.展开更多
The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent ed...The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper, we studied the upper bound of of Sn+1∨Pm and展开更多
A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges c...A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.展开更多
In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection meth...In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection method is the sarne as the algorithms without SRLG constraint. A problem of CSPS algorithm is that, after a primary path is selected, the success probability to select an SRLG-diverse backup path for it is low. If SRLG is taken into account when computing the primary path, then the probability to successfully select an SRLG-diverse backup path will be much increased. Based on this idea, an active SRLG-diverse path selection （ASPS） algorithm is proposed. To actively avoid selecting those SRLG links, when computing the primary path, a link that share risk with more links is assigned a larger link cost. To improve the resource utilization ratio, it is permitted that the bandwidth resources are shared among backup paths. What is more, differentiated reliability （DiR） requirements of different customers are considered in ASPS algorithm. The simulation results show that, compared with CSPS algorithm, ASPS algorithm not only increases successful protection probability but also improves resource utilization ratio.展开更多
A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It sim...A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It simultaneously optimizes multiple QoS objectives by a genetic algorithm in conjunction with concept of Pareto dominance. The simulation demonstrates that the proposed algorithm is capable of discovering a set of QoS-based near optimal paths within in a few iterations. In addition, the simulation results also show the scalability of the algorithm with increasing number of network nodes.展开更多
计算能力弱、存储容量小是普通物联网节点的典型特征,复杂的部署环境和不稳定的无线链路又会导致物联网网络状态频繁变化.所以,物联网中固定的传输路径无法提供高效的感知及数据传输服务.例如典型的树型路由结构中,靠近树根的节点要提...计算能力弱、存储容量小是普通物联网节点的典型特征,复杂的部署环境和不稳定的无线链路又会导致物联网网络状态频繁变化.所以,物联网中固定的传输路径无法提供高效的感知及数据传输服务.例如典型的树型路由结构中,靠近树根的节点要提供的传输任务较重,能量消耗更快,会导致整个网络部署周期变短.本文提出了一种路径可实时定义的物联网传输模型(IoT Transmission Model with Real-time Path Definition,ITRP),物联子网中所有节点将邻接关系上报给网关设备,由性能占优的有源供电网关设备来定义网络的实时路由树.网关向物联子网节点发送报文时会携带转发标签,后续转发节点只需根据标签完成报文传输,并根据上一跳信息建立其到网关的反向传输路径.ITRP模型可围绕特定的网络服务目标(节能、传输安全、带宽保障等)收集相关网络状态信息,并周期性调整路由拓扑,实现物联网传输服务的优化.实验面向能量均衡目标展开,经过10个信息采集周期,ITRP模型相对确定性路由模型能量最低节点的能耗比为44%~86%,相对自适应多径传输模型能量最低节点的能耗比为63%~86%;而且,ITRP模型只需较小的标签代价,实验环境中报文的平均标签长度不超过5比特.展开更多
文摘In 2012, Ponraj et al. defined a concept of k-product cordial labeling as follows: Let f be a map from V(G)to { 0,1,⋯,k−1 }where k is an integer, 1≤k≤| V(G) |. For each edge uvassign the label f(u)f(v)(modk). f is called a k-product cordial labeling if | vf(i)−vf(j) |≤1, and | ef(i)−ef(j) |≤1, i,j∈{ 0,1,⋯,k−1 }, where vf(x)and ef(x)denote the number of vertices and edges respectively labeled with x (x=0,1,⋯,k−1). Motivated by this concept, we further studied and established that several families of graphs admit k-product cordial labeling. In this paper, we show that the path graphs Pnadmit k-product cordial labeling.
基金Supported by the National Natural Science Foundation of China (60573089)the Teaching and Research Award Program for Out-standing Young Teachers in Post-Secondary Institutions by the Ministry of Education, China (706016)
文摘Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.
基金Supported in part by the NNSF of China(10301010,60673048)Science and Technology Commission of Shanghai Municipality(04JC14031).
文摘A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1097102510901035)
文摘For a graph G and two positive integers j and k, an m-L（j, k）-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L（j, k）-edge-labeling admitted by G.In this article, we study the L（1, 2）-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ？-regular trees and wheels.
文摘Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky graphical images transfer. Therefore, the policies of assigning traffic to various service classes and providing service as per the service level agreement of the user with the network provider came into existence. Multi-protocol Label Switching is the backbone of fast switching technology that helps the network service providers to implement these policies. It provides Quality of service oriented reserved paths from the source to the destination for the user’s traffic. Selection of these paths is a cumbersome task, especially when the traffic forecast is totally unknown. Furthermore, nodes and link failures in the Internet worsen the situation. This paper addresses the issue of selecting Label Switched Paths (LSPs) for various traffic demands in the network so that the resultant network has the characteristics like high failure resistance, low LSP demand blocking probability, low impact from the node or link failure, load balancing and low over-all resource utilization. By extensive simulations, the proposed cost function has been compared with the various cost functions mentioned in the literature and it was found to score over them in major aspects.
文摘The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper, we studied the upper bound of of Sn+1∨Pm and
文摘A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK-labeling. Let c:E(G)→ℕbe a proper edge coloring of G which induces a proper vertex coloring c′:V(G)→ℤndefined by c′(v)≡∑e∈Evc(e)modnSuch that Evis the set of edges incident with vin G. The minimum positive integer for which the graph G has NK-labeling called NK-chromatic index and denoted by χ′NK(G). We study the NK-labeling of several well-known classes of graphs. It is shown that the NK-chromatic of the path Pnfor n≥4is three and for odd n, the NK-chromatic of the complete graph Knis n. Other results dealing with the NK-labeling are also presented.
基金supported by the National Natural Science Foundation of China (60673142)Applied Basic ResearchProject of Sichuan Province (2006J13-067).
文摘In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection method is the sarne as the algorithms without SRLG constraint. A problem of CSPS algorithm is that, after a primary path is selected, the success probability to select an SRLG-diverse backup path for it is low. If SRLG is taken into account when computing the primary path, then the probability to successfully select an SRLG-diverse backup path will be much increased. Based on this idea, an active SRLG-diverse path selection （ASPS） algorithm is proposed. To actively avoid selecting those SRLG links, when computing the primary path, a link that share risk with more links is assigned a larger link cost. To improve the resource utilization ratio, it is permitted that the bandwidth resources are shared among backup paths. What is more, differentiated reliability （DiR） requirements of different customers are considered in ASPS algorithm. The simulation results show that, compared with CSPS algorithm, ASPS algorithm not only increases successful protection probability but also improves resource utilization ratio.
文摘A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It simultaneously optimizes multiple QoS objectives by a genetic algorithm in conjunction with concept of Pareto dominance. The simulation demonstrates that the proposed algorithm is capable of discovering a set of QoS-based near optimal paths within in a few iterations. In addition, the simulation results also show the scalability of the algorithm with increasing number of network nodes.
文摘计算能力弱、存储容量小是普通物联网节点的典型特征,复杂的部署环境和不稳定的无线链路又会导致物联网网络状态频繁变化.所以,物联网中固定的传输路径无法提供高效的感知及数据传输服务.例如典型的树型路由结构中,靠近树根的节点要提供的传输任务较重,能量消耗更快,会导致整个网络部署周期变短.本文提出了一种路径可实时定义的物联网传输模型(IoT Transmission Model with Real-time Path Definition,ITRP),物联子网中所有节点将邻接关系上报给网关设备,由性能占优的有源供电网关设备来定义网络的实时路由树.网关向物联子网节点发送报文时会携带转发标签,后续转发节点只需根据标签完成报文传输,并根据上一跳信息建立其到网关的反向传输路径.ITRP模型可围绕特定的网络服务目标(节能、传输安全、带宽保障等)收集相关网络状态信息,并周期性调整路由拓扑,实现物联网传输服务的优化.实验面向能量均衡目标展开,经过10个信息采集周期,ITRP模型相对确定性路由模型能量最低节点的能耗比为44%~86%,相对自适应多径传输模型能量最低节点的能耗比为63%~86%;而且,ITRP模型只需较小的标签代价,实验环境中报文的平均标签长度不超过5比特.
