求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.     

Synthesis of a linear controller for a control system with interval parameters on a base of D-partition in vertices of a coefficient's polyhedron of characteristic polynomial

The article deals with the technique developed for the parametric design of a robust controller which ensures the desired robust quality indicators in the system with interval parameters. This technique is based on the construction of the D-partition in the space of controller parameters at vertices of the coefficient polyhedron of a characteristic polynomial. Grounds for this are the fact that the interval system has its minimum degree of stability and maximum degree of oscillation at certain vertices of the specified polyhedron. To determine the minimum sets of those vertices, a new technique has been developed. The developed technique is based on inequalities obtained for outlet angles of the edge branches coming out from system poles, which determine the root indices of robust quality. Applying the developed technique for the vertex D-partition, the design of the PI controller of the stabilization system for a tethered underwater vehicle has been carried out. The results of the design confirm the efficiency of the developed approach.     

Optimal interval controller design for uncertain systems

The interval controller design is a hot issue for uncertain systems, whereas how to design an optimal interval controller under the premise of ensuring system stability is a difficult problem that needs further study. This paper mainly aims at the single input single output uncertain system to propose an optimal interval controller based on the Kharitonov theorem and an interval optimization algorithm, which can guarantee the stability and optimization of a closed-loop interval system. According to the Kharitonov theorem, the optimal interval controller design can be transformed into an optimal controller synthesis issue of multiple vertex objects. An interval particle swarm optimization (IPSO) algorithm is then used to optimize the quadratic performance index with interval variables for each vertex object to obtain the solution domains of the controller parameters, and the vertex method is utilized to prevent interval width expansion or divergence in the iteration. Finally, the intersections of the solution domains for all vertex objects are obtained as the optimal interval solution of interval controller parameters. In addition, the stability verification approach of the closed-loop system and the empirical rule to select the interval particle width are given. Simulation results for typical examples demonstrate that the designed interval controller not only performs optimally but also can robustly stabilize the interval system.     

Linear-time algorithms for eliminating claws in graphs

Since many -complete graph problems are polynomial-time solvable when restricted to claw-free graphs, we study the problem of determining the distance of a given graph to a claw-free graph, considering vertex elimination a measure. Claw-free Vertex Deletion (CFVD) consists of determining the minimum number of vertices to be removed from a graph such that the resulting graph is claw-free. Although CFVD is -hard in general and recognizing claw-free graphs is still a challenge, where the current best deterministic algorithm for a graph G consists of performing executions of the best algorithm for matrix multiplication, we present linear-time algorithms for CFVD on weighted block graphs and weighted graphs with bounded treewidth. Furthermore, we show that this problem on forests can be solved in linear time by a simpler algorithm, and we determine the exact values for full k-ary trees. On the other hand, we show that CFVD is -hard even when the input graph is a split graph. We also show that the problem is hard to be approximated within any constant factor better than 2, assuming the unique games conjecture.