Geometry of tropical moduli spaces and linkage of graphs

We prove the following “linkage” theorem: two p-regular graphs of the same genus can be obtained from one another by a finite alternating sequence of one-edge-contractions; moreover this preserves 3-edge-connectivity. We use the linkage theorem to prove that various moduli spaces of tropical curves are connected through codimension one.     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

Finding dominators via disjoint set union

The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorithms exist, they use sophisticated data structures. We develop an algorithm for finding dominators that uses only a “static tree” disjoint set data structure in addition to simple lists and maps. The algorithm runs in near-linear or linear time, depending on the implementation of the disjoint set data structure. We give several versions of the algorithm, including one that computes loop nesting information (needed in many kinds of global code optimization) and that can be made self-certifying, so that the correctness of the computed dominators is very easy to verify.     

Polynomials with graphs of maximum length

In this paper we find the pairs of functionsg, G (g<G) such that the maximum length of the graph of polynomials of given degree contained betweeng andG is attained on one of the two snakes generated by the functionsg andG. Translated fromMatematicheskie Zametki, Vol. 65, No. 1, pp. 61–69, January, 1999.     

λKv的最大K2,3填充设计和最小K2,3覆盖设计

对于一个有限简单图G,λK_v的G-设计(G-填充,G-覆盖),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是一个(X,B),其中X是K_v的顶点集,B是K_v的子图族,每个子图(称为区组)均同构于G,且K_v中任一边都恰好(最多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为是最大(最小)的,如果没有其它的这种填充(覆盖)设计具有更多(更少)的区组.本文对于λ>1确定了(v,K_2,3,λ)-GD的存在谱,并对任意λ构造了λK_v的最大K_2,3-填充设计和最小K_2,3-覆盖设计.     

一种新的膜系设计方法——Needle法

Ｎｅｅｄｌｅ法是一种先进的膜系设计方法，它克服了传统优化方法容易陷入局部极值的缺点，通过在膜系中插入薄层，使得评价函数降低，优化设计可以从任意给定的一层膜开始，文中给出了其数学模型及详细的推导。     

Computer-aided spillway design using the boundary element method and non-linear programming

The general context of this paper is to support the design of spillways by a direct mathematical approach instead of trial-and-error methods. First, a two-dimensional model is formulated to determine the free surface and the discharge for a stationary, incompressible, homogeneous, non-viscous and irrotational flow over a fixed spillway. The flow satisfies the Laplace equation and the Bernoulli equation (potential flow). An important feature of the model is that it can be extended to design the spillway structure when the spillway is not fixed but the pressure on the spillway is described by a cavitation criterion. Next, the continuous model is discretized by the boundary element method (BEM). We use a non-linear programming algorithm to calculate the pressures and the shape of the spillway. A computer-aided design package is developed on a PC using the equations describing the free surface, the BEM and standard optimization techniques. The input and output of the model are realized using graphical routines. Finally, we discuss the convergence and the computation time of the algorithms.     

On the determination and construction of optimal row-column designs having unequal row and column sizes

In this paper we consider experimental situations requiring usage of a row-column design where v treatments are to be applied to experimental units arranged in b ₁ rows and b ₂ columns where row i has size k _1i , i=1,..., b ₁ and column j has size k _2j , j=1,..., b ₂. Conditions analogous to those given in Kunert (1983, Ann. Statis., 11, 247–257) and Cheng (1978, Ann. Statist., 6, 1262–1272) are given which can often be used to establish the optimality of a given row-column design from the optimality of an associated block design. In addition, sufficient conditions are derived which guarantee the existence of an optimal row-column design which can be constructed by appropriately arranging treatments within blocks of an optimal block design.Visiting from the Indian Statistical Institute.     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).