Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs

In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST₂-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST₂-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST₂-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.     

A Mixed Heuristic for Circuit Partitioning

As general-purpose parallel computers are increasingly being used to speed up different VLSI applications, the development of parallel algorithms for circuit testing, logic minimization and simulation, HDL-based synthesis, etc. is currently a field of increasing research activity. This paper describes a circuit partitioning algorithm which mixes Simulated Annealing (SA) and Tabu Search (TS) heuristics. The goal of such an algorithm is to obtain a balanced distribution of the target circuit among the processors of the multicomputer allowing a parallel CAD application for Test Pattern Generation to provide good efficiency. The results obtained indicate that the proposed algorithm outperforms both a pure Simulated Annealing and a Tabu Search. Moreover, the usefulness of the algorithm in providing a balanced workload distribution is demonstrated by the efficiency results obtained by a topological partitioning parallel test-pattern generator in which the proposed algorithm has been included. An extented algorithm that works with general graphs to compare our approach with other state of the art algorithms has been also included.     

蔡氏对偶混沌电路分析

提出了一个新颖的蔡氏对偶混沌电路,并进行了深入的理论研究和计算机仿真分析.得出了几点结论:1)此混沌电路元器件少,且与蔡氏混沌电路结构完全对偶.2)在确定的元器件参数条件下,电路出现双涡卷奇怪吸引子和丰富的混沌动力学行为. 关键词： 蔡氏对偶电路 奇怪吸引子 混沌     

On hyperbolic once-punctured-torus bundles II: fractal tessellations of the plane

We describe fractal tessellations of the complex plane that arise naturally from Cannon–Thurston maps associated to complete, hyperbolic, once-punctured-torus bundles. We determine the symmetry groups of these tessellations. To our wives, Ardyth and Elena.     

Cubic planar hamiltonian graphs of various types

Let U be the set of cubic planar hamiltonian graphs, A the set of graphs G in U such that G-v is hamiltonian for any vertex v of G, B the set of graphs G in U such that G-e is hamiltonian for any edge e of G, and C the set of graphs G in U such that there is a hamiltonian path between any two different vertices of G. With the inclusion and/or exclusion of the sets A,B, and C, U is divided into eight subsets. In this paper, we prove that there is an infinite number of graphs in each of the eight subsets.     

Comparison of experimental data with the numerical simulation of planar entry flow: Role of the constitutive equation

The goal of this research was to determine whether there is any interaction between the type of constitutive equation used and the degree of mesh refinement, as well as how the type of constitutive equation might affect the convergence and quality of the solution, for a planar 4:1 contraction in the finite eiement method. Five constitutive equations were used in this work: the Phan-Thien–Tanner (PTT), Johnson–Segalman (JS), White–Metzner (WM), Leonov-like and upper convected Maxwell (UCM) models. A penalty Galerkin finite element technique was used to solve the system of non-linear differential equations. The constitutive equations were fitted to the steady shear viscosity and normal stress data for a polystyrene melt. In general it was found that the convergence limit based on the Deborah number De and the Weissenberg number We varied from model to model and from mesh to mesh. From a practical point of view it was observed that the wall shear stress in the downstream region should also be indicated at the point where convergence is lost, since this parameter reflects the throughput conditions. Because of the dependence of convergence on the combination of mesh size and constitutive equation, predictions of the computations were compared with birefringence data obtained for the same polystyrene melt flowing through a 4:1 planar contraction. Refinement in the mesh led to better agreement between the predictions using the PTT model and flow birefringence, but the oscillations became worse in the corner region as the mesh was further refined, eventually leading to the loss of convergence of the numerical algorithm. In comparing results using different models at the same wall shear stress conditions and on the same mesh, it was found that the PTT model gave less overshoot of the stresses at the re-entrant corner. Away from the corner there were very small differences between the quality of the solutions obtained using different models. All the models predicted solutions with oscillations. However, the values of the solutions oscillated around the experimental birefringence data, even when the numerical algorithm would not converge. Whereas the stresses are predicted to oscillate, the streamlines and velocity field remained smooth. Predictions for the existence of vortices as well as for the entrance pressure loss (ΔP_ent) varied from model to model. The UCM and WM models predicted negative values for ΔP_ent.     

The planar algebra of a semisimple and cosemisimple Hopf algebra

To a semisimple and cosemisimple Hopf algebra over an algebraically closed field, we associate a planar algebra defined by generators and relations and show that it is a connected, irreducible, spherical, non-degenerate planar algebra with non-zero modulus and of depth two. This association is shown to yield a bijection between (the isomorphism classes, on both sides, of) such objects.     

The Analysis and Calculation on ECRH Anode Circuit on the HL-2A Tokamak

In the last year, ECRH system has been built in the HL-2A and the testing of gyrotron is also finished. In the project testing, one of the problems is current-peak occurring in the anode circuit of gyrotron. The current-peak is much larger than that of the value set in protection circuit. The frequent current-peak frequently occurring in the rising of anode-voltage often caused the protection circuit to mistaken trigger. The mistaken triggering often halted the normal gyrotron-testing. A set of equations of anode circuit are derived for analysis the phenomena of the current-peak. The calculation based on the deduced formula shows that value of the current-peak strongly depends on the inductance L, capacitance C and the ramp-time of anode voltage in the anode circuit. The conductance L and capacitance C are the characteristic inductance and capacitance of the cable that is used for anode HV power supply. The numerical calculation is exactly consistent with waveform of the current peak recorded by oscillograph, that means the derived formula are correct. In order to decrease the value of the current-peak, we should decrease capacitance C, and increase inductance L and ramp-time of anode voltage.     

THE MAXIMUM NUMBER OF INTERSECTIONS BETWEEN TWO PLANE RECTANGULAR PATHS

We show that the maximum number of intersections between two plane rectangular paths with lengths m and n: 2 ≤ m ≤ n, is 4n 2, if m=4 and n≡1(mod 3); and it is mn 1 otherwise.     

耦合映象格子时空行为的电路仿真实验

设计以一维逻辑斯蒂离散电路作为元胞子电路的耦合格子时空电路系统,利用PSPICE仿真平台,观测到该电路系统存在的各种时空动力学行为.仿真实验结果与计算机数值计算结果一致.