Block transitive Steiner systems with more than one point orbit

For all ‘reasonable’ finite t, k, and s, we construct a t‐(?₀, k, 1) design and a group of automorphisms which is transitive on blocks and has s orbits on points. In particular, there is a 2‐(?0, 4, 1) design with a block‐transitive group of automorphisms having two point orbits. This answers a question of P. J. Cameron and C. E. Praeger. The construction is presented in a purely combinatorial way, but is a by‐product of a new way of looking at a model‐theoretic construction of E. Hrushovski. © 2004 Wiley Periodicals, Inc.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

Embedding partial Steiner triple systems so that their automorphisms extend

It is shown that there is a function g on the natural numbers such that a partial Steiner triple system U on u points can be embedded in a Steiner triple system V on ν points, in such a way that all automorphisms of U can be extended to V, for every admissible ν satisfying ν > g(u). We find exponential upper and lower bounds for g. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Infinite classes of anti‐mitre and 5‐sparse Steiner triple systems

In this paper, we present three constructions for anti‐mitre Steiner triple systems and a construction for 5‐sparse ones. The first construction for anti‐mitre STSs settles two of the four unsettled admissible residue classes modulo 18 and the second construction covers such a class modulo 36. The third construction generates many infinite classes of anti‐mitre STSs in the remaining possible orders. As a consequence of these three constructions we can construct anti‐mitre systems for at least 13/14 of the admissible orders. For 5‐sparse STS(υ), we give a construction for υ ≡ 1, 19 (mod 54) and υ ≠ 109. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 237–250, 2006     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].