Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

PS_N is a fast forward permutation if for each m the computational complexity of evaluating P^m(x) is small independently of m and x. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in S_N is Θ(N) if one does not use queries of the form P^m(x), but is only Θ(1) if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form P^m(x) are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.     

New Results on the Queens_n 2 Graph Coloring Problem

For the Queens_n ² graph coloring problems no chromatic numbers are available for n > 9 except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14.     

Surface roughness investigation of semi-conductor wafers

Conventionally, surface roughness is predominantly determined through the use of stylus instruments. However, there are certain limitations involved in the method, particularly when a test specimen, such as a silicon wafer, has a smooth mirror-like surface. Hence, it is necessary to explore alternative non-contact techniques. Light scattering has recently been gaining popularity as an optical technique to provide prompt and precise inspection of surface roughness. In this paper, the total integrated scattering (TIS) model is modified to retrieve parameters on surface micro-topography through light scattering. The applicability of the proposed modified TIS model is studied and compared with an atomic force microscope. Experimental results obtained show that the proposed technique is highly accurate for measuring surface roughness in the nanometer range.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Constructing two-weight codes with prescribed groups of automorphisms

We construct new linear two-weight codes over the finite field with q elements. To do so we solve the equivalent problem of finding point sets in the projective geometry with certain intersection properties. These point sets are in bijection to solutions of a Diophantine linear system of equations. To reduce the size of the system of equations we restrict the search for solutions to solutions with special symmetries.Two-weight codes can be used to define strongly regular graphs. We give tables of the two-weight codes and the corresponding strongly regular graphs. In some cases we find new distance-optimal two-weight codes and also new strongly regular graphs.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

HL－1装置辅助加热等对能量约束的影响

在ＨＬ－１托卡马克上进行了辅助加热、加料、电流驱动的物理实验研究。在改善等离子体约束方面，某些实验取得了较好的结果。在适当的稳定放电条件下，低杂波电流驱动和弹丸注入辅助加料，均能使等离子体能量约束得到一定程度的改善，与相同密度条件下的欧姆加热放电相比，能量约束时间提高了约３０％。在电子回旋共振加热等离子体实验中，等离子体总能量明显增加，但与相同密度条件下的欧姆加热放电相比，能量约束时间减少了约２０％。     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．     

A census of semisymmetric cubic graphs on up to 768 vertices

A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K_1,3 as a normal quotient is investigated in detail. Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201) Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506. Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University of Auckland for hospitality during his visit there in 2003.     

First Total Synthesis of 12-Hydroxy-13-methylpodocarpa-9, 11, 13-trien-3-one

12-Hydroxy-13-methylpodocarpa-9, 11, 13-trien-3-one 9 was isolated from the twigs ofCroton salutaris1. Many diterpenes exhibit significant bioactivities, such as antibac-terial and antitumour and 9 has a rare structure. In order to study the relationshipb…