Modern computing systems typically use a large number of independent, non-identical computing nodes to perform a set of coordinated computations in parallel. The computing system and its constituent computing nodes often exhibit more than two performance levels or states corresponding to different computing powers. This paper models and evaluates performability of largescale multi-state computing systems, which is the probability that a computing system performs at a particular performance level. The heterogeneity in the constituent components of different nodes (due to factors such as different model generations, model suppliers, and operating environments) makes performability analysis difficult and challenging. In this paper a specification method for system performance level (SPL) is first introduced. A multi-valued decision diagram (MDD) based approach is then proposed for performability analysis of multi-state computing systems consisting of nodes with different state occupation probabilities, which encompasses novel and efficient MDD model generation procedures. Example and benchmark studies are performed to show that the proposed approach can offer efficient performability analysis of large-scale computing systems.

A vertex set S⊆V(G) is k-weak-edge-connected if, for every C⊂Sand x∈S−C, there are min{k,|C|} edge-disjoint (x, C)-paths in G. For a graph G and a k-weak-edge-connected vertex set S⊂V(G) with k≥3 and 4≤|S|≤2k, we show that G has an Eulerian subgraph containing all vertices in S.

A subset is called an -vertex-cut of if is disconnected and each vertex has at least two neighbors in . The cardinality of a minimum -vertex-cut of , denoted by , is the -vertex-connectivity of . In this work, we prove that for , where is the -dimensional star graph.

A vertex set F is a k-path vertex cover () of graph G if every path of G on k vertices contains at least one vertex from F. A graph G is a d-dimensional ball graph if each vertex of G corresponds to a ball in , two vertices are adjacent in G if and only if their corresponding balls have nonempty intersection. The heterogeneity of a ball graph is defined to be , where and are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum problem in a ball graph whose heterogeneity is bounded by a constant.

在无线传感器网络中应用虚拟骨干，可以有效地节约能量、减少干扰、延长网络寿命，在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展，侧重于研究方法和理论结果，为相关研究人员提供参考.