Solving the 2-rooted mini-max spanning forest problem by branch-and-bound

The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes.     

基于二维细分技术的时栅信号处理系统设计

为了提高时栅位移传感器的动态性能及测量精度,提出了一种基于FPGA和二维细分技术的时栅位移传感器信号处理系统。利用二维细分技术对插补脉冲进行倍频处理,降低了对插补脉冲频率的要求,通过倍频后的高频脉冲插补时栅感应信号和参考信号之间的相位差完成了时栅角位移的测量,提高测量精度。该系统在FPGA内基于NiosII软核完成数据的采集和处理,简化了系统,并加入自定义指令提高了数据处理效率。实验表明,采用该系统后,时栅位移传感器在960MHz插补脉冲下测量误差峰峰值为±1.3″,实现了时栅的高精度角位移测量。     

Traceability of line graphs

Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L(G) its line graph. If n is sufficiently large and, either ; or and G is almost bridgeless, then L(G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

Stable routing under the Spanning Tree Protocol

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.     

Characterization of some convergent bivariate subdivision schemes with nonnegative masks

Knowing that the convergence of a multivariate subdivision scheme with a nonnegative mask can be characterized by whether or not some finite products of row-stochastic matrices induced by this mask have a positive column. However, the number of those products is exponential with respect to the size of matrices. For nonnegative univariate subdivision, this problem is completely solved. Thus, the convergence in this case can be checked in linear time with respect to the size of a square matrix. This paper will demonstrate the necessary and sufficient conditions for the convergence of some nonnegative bivariate subdivision schemes by means of the so-called connectivity of a square matrix, which is derived by a given mask. Moreover, the connectivity can be examined in linear time with respect to the size of this matrix.