直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性(英文)

给定一个简单图G和正整数k,具有完美匹配的图G的k-导出匹配划分是对顶点集V(G)的一个k-划分(V_1,V_2,…,V_k),其中对每一个i(1≤i≤k),由V_i导出的G的子图G[V_i]是1-正则的.k-导出匹配划分问题是指对给定的图G,判定G是否存在一个k-导出匹配划分.令M_1,M_2,…,M_k为图G的k个导出匹配,如果V(M_1)∪V(M_2)∪…∪V(M_k)=V(G),则我们称{M_1,M_2…,M_k}是G的k-导出匹配覆盖. k-导出匹配覆盖问题是指对给定的图G,判定G是否存在k-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2-划分问题和导出匹配2-覆盖问题都是NP-完全的.

一种支持资源跨域共享的制造网格平台

由于地区间服务资源的不均衡,如何实现地区间服务资源的共享,为本地和异地企业提供更多、更廉价的服务,日益成为政府需要破解的难题。针对这一问题,文中提出一种支持资源跨域共享的区域制造网格应用平台。对平台建立的资源聚集和业务协同环境,提出了一种制造网格体系结构,对平台的业务模式进行描述,并分析了实现平台的关键使能技术。区域制造网格平台的建立克服了网络化制造中的带宽瓶颈和服务能力不足的缺陷,实现了更高的访问速度与容错性,能够确保地区之间制造资源的共享与分配。从平台部署实施的应用结果表明,该平台对中小制造企业间实现制造资源跨区域共享起到了较好的作用。最后,分析了平台应用中存在的不足,并对下一步的工作进行了展望。

一种基于移动P2P平台的无线传感器网络体系结构

借助P2P思想,构建一个基于移动网络基础设施提供对等服务的无线传感器网络体系结构。移动网络充当移动P2P平台,提供一种普适的传感器组网。代表传感器网络的网关节点隐藏了其实现细节,在P2P模式工作下向用户提供更加优质的个人服务。此外,还讨论了服务平台构建过程中的一般性问题。