Large sets of Hamilton cycle and path decompositions

The existence spectrums for large sets of Hamilton cycle decompositions and Hamilton path decompositions are completed. Also, we show that the completion of large sets of directed Hamilton cycle decompositions and directed Hamilton path decompositions depends on the existence of certain special tuscan squares. Several conjectures about special tuscan squares are posed.     

Path coupling using stopping times and counting independent sets and colorings in hypergraphs

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree Δ of a vertex and the minimum size m of an edge satisfy m ≥ 2Δ + 1. We also show that the Glauber dynamics for proper q‐colorings of a hypergraph mixes rapidly if m ≥ 4 and q > Δ, and if m = 3 and q ≥ 1.65Δ. We give related results on the hardness of exact and approximate counting for both problems. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Behavior of a quantum particle in contact with a classical heat bath

We investigate the behavior of a two-level quantum system in contact with a classical heat bath, e.g., a solute particle with internal degrees of freedom immersed in a solvent of massive particles. Using a combination of analytical and numerical methods, we obtain precise information about localization, time-displaced correlation functions, and the frequency-dependent susceptibility of such solute particles. We find that these quantities can have a strong dependence on the density of the solvent fluid, with the maximum changes from the behavior of the corresponding isolated quantum system occurring in many cases at very low densities. We compare the exact results with those obtained by path integral Monte Carlo. There is good agreement with the imaginary time correlations, but analytic continuation to real time proves elusive: even with the best numerical data on the former, we can only get very gross features of the latter.     

余代数上余倾斜余模的结构

研究了余代数上余倾斜余模的结构特征,证明了每个余倾斜余模都可以写成不可分解的两两非同构的余模的直和形式,每个余倾斜余模包含所有的内射不可分解模作为直和项.最后构造了余倾斜余模的两个例子.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.     

Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model

The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.’s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model.     

Proper generating trees and their internal path length

We find the generating function counting the total internal path length of any proper generating tree. This function is expressed in terms of the functions (d(t),h(t)) defining the associated proper Riordan array. This result is important in the theory of Riordan arrays and has several combinatorial interpretations.     

对Floyd算法的两点注记

本给Floyd算法配置了一种更便于使用的路径标记方法，还给出了在无向网络上减少Floyd算法的计算量的方法。     

Adler-Bardeen theorem in path integral formulation

The higher order contributions to Jacobian in Fujikawa’s path integral framework is considered and the form of anomaly equation in higher orders is established. An argument for the Adler-Bardeen theorem in this formulation is given.     

Tilting modules over path algebras of Dynkin type and complete slice modules

Let T be a tilting A-module over a path algebra of Dynkin type.We prove thatif the indecomposable direct summands of T are in the different (?)-orbits of the AR-quiverof A,then T is a complete slice module.