A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

Non-Euler–Lagrangian Pareto-optimality Conditions for Dynamic Multiple Criterion Decision Problems

In this paper the problem of verifying the Pareto-optimality of a given solution to a dynamic multiple-criterion decision (DMCD) problem is investigated. For this purpose, some new conditions are derived for Pareto-optimality of DMCD problems. In the literature, Pareto-optimality is characterized by means of Euler-Lagrangian differential equations. There exist problems in production and inventory control to which these conditions cannot be applied directly (Song 1997). Thus, it is necessary to explore new conditions for Pareto-optimality of DMCD problems. With some mild assumptions on the objective functionals, we develop necessary and/or sufficient conditions for Pareto-optimality in the sprit of optimization theory. Both linear and non-linear cases are considered.     

纳米颗粒悬浮液池内泡状沸腾的实验研究

本文对纳米颗粒悬浮液在平壁面上池内沸腾进行了实验研究。实验用的纳米粒子为26 nm的铁粉和13 nm的三氧化二铝纳米粉末,基液为去离子水。分别配成体积浓度为0．1％, 1％和2％的悬浮液。实验结果表明,纳米悬浮颗粒对液体沸腾换热过程的影响会随着纳米颗粒性质,颗粒浓度及热流密度大小的不同而出现不同的效果;加入纳米颗粒后, 对基液沸腾换热的影响存在着两个相反的作用机制,它们分别为:纳米颗粒增强了液体内部的热量迁移能力(热物性的影响)和改变了加热面的表面结构特性(加热面特性的影响)。     

Asymmetric responses of international stock markets to trading volume

The major goal of this paper is to examine the hypothesis that stock returns and return volatility are asymmetric, threshold nonlinear, functions of change in trading volume. A minor goal is to examine whether return spillover effects also display such asymmetry. Employing a double-threshold GARCH model with trading volume as a threshold variable, we find strong evidence supporting this hypothesis in five international market return series. Asymmetric causality tests lend further support to our trading volume threshold model and conclusions. Specifically, an increase in volume is positively associated, while decreasing volume is negatively associated, with the major price index in four of the five markets. The volatility of each series also displays an asymmetric reaction, four of the markets display higher volatility following increases in trading volume. Using posterior odds ratio, the proposed threshold model is strongly favored in three of the five markets, compared to a US news double threshold GARCH model and a symmetric GARCH model. We also find significant nonlinear asymmetric return spillover effects from the US market.     

Biham–Middleton–Levine model with four-directional traffic

We study the four-directional traffic flow on a two-dimensional lattice. In the case of discrete densities, we assume equal number of vehicles in each lane. Except for the minimum density, the gridlock emerges swiftly. Two kinds of gridlock have been observed. The global gridlock dominates the system when the density is twice the minimum value. At higher densities, the system is pervaded by local gridlocks. We also analyze the time evolution of average speed. In the case of continuous densities, the vehicle numbers vary from lane to lane. The global gridlock is then destroyed by the fluctuations; while the local gridlock can still be observed.     

Ag纳米颗粒的光吸收和透射电镜研究

用硼氢化钠作还原剂,制备出两种相对稳定的含银纳米颗粒的水溶胶,用透射电镜（TEM）和光学吸收谱对这些颗粒进行了表征.当被还原的银离子较少时,所形成的银纳米颗粒较小,吸收峰呈现二极等离子体共振吸收峰.当被还原的银离子较多时,银纳米颗粒尺寸变大,并出现二极和四极共振吸收峰.在Ag纳米颗粒形成后,对其溶液稀释,发现其峰形保持不变,而峰位会出现红移,最大红移量可达到10 nm.透射电镜研究表明,低浓度溶胶中的Ag纳米颗粒尺寸较为均匀,平均直径12 nm.高浓度溶胶中的纳米颗粒尺寸呈双尺寸分布特点,少量颗粒直径小于14 nm,大部分颗粒直径大于20 nm.     

Effect of external Gaussian random field on phonon spectrum of linear atomic chains

We present the theoretical study of the effect of external random field characterized by a Gaussian probability distribution function on the continuous phonon spectrum of one-dimensional (1D) chain, based on the Jacobian matrix method. The cumulative effect of the random field and simple isotopic defect is studied analytically and numerically. The Gaussian random field removes a square-root divergence appearing in the phonon spectrum of ideal 1D chain. The impurity phonon DOS shows strong dependence on the variance and the mean of the random field and exhibits very different behavior from the non-random case: the continuous spectrum is expanded and the δ-peak, describing discrete impurity vibrations in the non-random chain with the impurity, falls into a continuous zone.     

Towards the Exact Minimization of BDDs—An Elitism-Based Distributed Evolutionary Algorithm

Binary Decision Diagrams (BDDs) are the state-of-the-art data structure for representation and manipulation of Boolean functions. In general, exact BDD minimization is NP-complete. For BDD-based technology, a small improvement in the number of nodes often simplifies the follow-up problem tremendously. This paper proposes an elitism-based evolutionary algorithm (EBEA) for BDD minimization. It can efficiently find the optimal orderings of variables for all LGSynth91 benchmark circuits with a known minimum size. Moreover, we develop a distributed model of EBEA, DEBEA, which obtains the best-ever variable orders for almost all benchmarks in the LGSynth91. Experimental results show that DEBEA is able to achieve super-linear performance compared to EBEA for some hard benchmarks.     

Surface profile measurement of low-frequency vibrating objects using temporal analysis of fringe pattern

A simple and accurate algorithm (phase scanning method) is proposed for 3D surface contouring and dynamic response determination of a vibrating object. A sinusoidal fringe pattern is projected onto a low-frequency vibrating object by a programmable liquid crystal display projector. The fringe patterns are captured by a high-speed CCD camera with a telecentric gauging lens. Phase values are evaluated point by point using phase scanning method. From the phase values of each point on the object, the contour of the specimen at different instants of vibration can be retrieved. In this paper, a small vibrating coin is used to demonstrate the validity of the method and the experimental results are compared with test results on a stationary coin using four-step phase shifting and fast Fourier transform methods. The technique is especially useful in applications where the vibrating object has a complicated shape.