Unique Covering Problems with Geometric Sets

The Exact Cover problem takes a universe U of n elements, a family F of m subsets of U and a positive integer k, and decides whether there exists a subfamily(set cover) F' of size at most k such that each element is covered by exactly one set. The Unique Cover problem also takes the same input and decides whether there is a subfamily F' subset of F such that at least k of the elements F' covers are covered uniquely(by exactly one set). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, Exact Cover is W1]-hard. While Unique Cover is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property Pi. Specifically, we consider the universe to be a set of n points in a real space R-d, d being a positive integer. When d = 2 we consider the problem when. requires all sets to be unit squares or lines. When d > 2, we consider the problem where. requires all sets to be hyperplanes in R-d. These special versions of the problems are also known to be NP-complete. When parameterizing by k, the Unique Cover problem has a polynomial size kernel for all the above geometric versions. The Exact Cover problem turns out to be W1]-hard for squares, but FPT for lines and hyperplanes. Further, we also consider the Unique Set Cover problem, which takes the same input and decides whether there is a set cover which covers at least k elements uniquely. To the best of our knowledge, this is a new problem, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W1]-hard in the abstract setting, when parameterized by k. However, when we restrict ourselves to the lines and hyperplanes versions, we obtain FPT algorithms.

Onset of plane layer magnetoconvection at low Ekman number

We study the onset of magnetoconvection between two infinite horizontal planes subject to a vertical magnetic field aligned with background rotation. In order to gain insight into the convection taking place in the Earth's tangent cylinder, we target regimes of asymptotically strong rotation. The critical Rayleigh number Ra-c and critical wavenumber a(c) are computed numerically by solving the linear stability problem in a systematic way, with either stress-free or no-slip kinematic boundary conditions. A parametric study is conducted, varying the Ekman number E (ratio of viscous to Coriolis forces) and the Elsasser number. (ratio of the Lorentz force to the Coriolis force). E is varied from 10(-9) to 10(-2) and. from 10(-3) to 1. For a wide range of thermal and magnetic Prandtl numbers, our results verify and confirm previous experimental and theoretical results showing the existence of two distinct unstable modes at low values of E-one being controlled by the magnetic field, the other being controlled by viscosity (often called the viscous mode). It is shown that oscillatory onset does not occur in the range of parameters we are interested in. Asymptotic scalings for the onset of these modes are numerically confirmed and their domain of validity is precisely quantified. We show that with no-slip boundary conditions, the asymptotic behavior is reached for E < 10(-6) and establish a map in the (E, Lambda) plane. We distinguish regions where convection sets in either through the magnetic mode or through the viscous mode. Our analysis gives the regime in which the transition between magnetic and viscous modes may be observed. We also show that within the asymptotic regime, the role played by the kinematic boundary conditions is minimal. (C) 2015 AIP Publishing LLC.

Size Effects on Strength in the Transition from Single-to-Polycrystalline Behavior

During the transition from single crystalline to polycrystalline behavior, the available data show the strength increasing or decreasing as the number of grains in a cross section is reduced. Tensile experiments were conducted on polycrystalline Ni with grain sizes (d) between 16 and 140 mu m and varying specimen thickness (t), covering a range of lambda (-t/d) between similar to 0.5 and 20. With a decrease in lambda, the data revealed a consistent trend of strength being independent of lambda at large lambda, an increase in strength, and then a decrease in strength. Microstructural studies revealed that lower constraints enabled easier rotation of the surface grains and texture evolution, independent of the specimen thickness. In specimen interiors, there was a greater ease of rotation in thinner samples. Measurements of misorientation deviations within grains revealed important differences in the specimen interiors. A simple model is developed taking into account the additional geometrically necessary dislocations due to variations in the behavior of surface and interior grains, leading to additional strengthening. A suitable combination of this strengthening and surface weakening can give rise to wide range of possibilities with a decrease in lambda, including weakening, strengthening, and strengthening and weakening.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

An analysis on overall crack-number-density of short-fatigue-cracks

The evolution of dispersed short-fatigue-cracks is analysed based on the equilibrium of crack-number-density (CND). By separating the mean value and the stochastic fluctuation of local CND, the equilibrium equation of overall CND is derived. Comparing with the mean-field equilibrium equation, the equilibrium equation of overall CND has different forms in the expression of crack-nucleation-rate or crack-growth-rate. The simulation results are compared with experimental measurements showing the stochastic analyses provide consistent tendency with experiments. The discrepancy in simulation results between overall CND and mean-field CND is discussed.

Generalization of Response Number for Dynamic Plastic Response of Shells Subjected to impulsive Loading

A dimensionless number, termed as response number in Zhao [Archive of Applied Mechanics 68 (1998) 524], has been suggested for the dynamic plastic response of beams and plates made up of rigidly perfect plastic materials subjected to dynamic loading. Many theoretical and experimental results can be reformulated into new concise forms with the response number. The concept of a new dimensionless number, response number, termed as Rn(n), is generalized in Zhao [Forschung im Ingenieurwesen 65 (1999) 107] to study the elastic, plastic, dynamic elastic as well as dynamic plastic buckling problems of columns, plates as well as shells. The response number Rn(n) is generalized to the dynamic behaviour of shells of various shapes in the present paper.

Application of response number for dynamic plastic response of plates subjected to impulsive loading

A dimensionless number, termed response number, is applied to the dynamic plastic response of plates subjected to dynamic loading. Many theoretical and experimental results presented by different researchers are reformulated into new concise forms with the response number. The advantage of the new forms is twofold: (1) they are more physically meaningful, and (2) they are independent of the choice of units, thus, they have wider range of applications.

Effect of liquid bridge volume on the instability in small-Prandtl-number half zones

A perturbation method is used to examine the linear instability of thermocapillary convection in a liquid bridge of floating half-zone filled with a small Prandtl number fluid. The influence of liquid bridge volume on critical Marangoni number and flow features is analyzed. The neutral modes show that the instability is mainly caused by the bulk flow that is driven by the nonuniform thermocapillary forces acting on the free surface. The hydrodynamic instability is dominant in the case of small Prandtl number fluid and the first instability mode is a stationary bifurcation. The azimuthal wave number for the most dangerous mode depends on the liquid bridge volume, and is not always two as in the case of a cylindrical liquid bridge with aspect ratio near 0.6. Its value may be equal to unity when the liquid bridge is relatively slender.

Transposon mutagenesis in a hyper-invasive clinical isolate of Campylobacter jejuni reveals a number of genes with potential roles in invasion.

Transposon mutagenesis has been applied to a hyper-invasive clinical isolate of Campylobacter jejuni, 01/51. A random transposon mutant library was screened in an in vitro assay of invasion and 26 mutants with a significant reduction in invasion were identified. Given that the invasion potential of C. jejuni is relatively poor compared to other enteric pathogens, the use of a hyper-invasive strain was advantageous as it greatly facilitated the identification of mutants with reduced invasion. The location of the transposon insertion in 23 of these mutants has been determined; all but three of the insertions are in genes also present in the genome-sequenced strain NCTC 11168. Eight of the mutants contain transposon insertions in one region of the genome (approximately 14 kb), which when compared with the genome of NCTC 11168 overlaps with one of the previously reported plasticity regions and is likely to be involved in genomic variation between strains. Further characterization of one of the mutants within this region has identified a gene that might be involved in adhesion to host cells.

Optimized Group Velocity Control Scheme and DNS of Decaying Compressible Turbulence of Relative High Turbulent Mach Number

To overcome the difficulty in the DNS of compressible turbulence at high turbulent Mach number, a new difference scheme called GVC8 is developed. We have succeeded in the direct numerical simulation of decaying compressible turbulence up to turbulent Mach number 0.95. The statistical quantities thus obtained at lower turbulent Mach number agree well with those from previous authors with the same initial conditions, but they are limited to simulate at lower turbulent Mach numbers due to the so-called start-up problem. The energy spectrum and coherent structure of compressible turbulent flow are analysed. The scaling law of compressible turbulence is studied. The computed results indicate that the extended self-similarity holds in decaying compressible turbulence despite the occurrence of shocklets, and compressibility has little effects on relative scaling exponents when turbulent Mach number is not very high.

Suggestion of a new dimensionless number for dynamic plastic response of beams and plates

A dimensionless number, termed response number in the present paper, is suggested for the dynamic plastic response of beams and plates made of rigid-perfectly plastic materials subjected to dynamic loading. It is obtained at dimensional reduction of the basic governing equations of beams and plates. The number is defined as the product of the Johnson's damage number and the square of the half of the slenderness ratio for a beam; the product of the damage number and the square of the half of the aspect ratio for a plate or membrane loaded dynamically. Response number can also be considered as the ratio of the inertia force at the impulsive loading to the plastic limit load of the structure. Three aspects are reflected in this dimensionless number: the inertia of the applied dynamic loading, the resistance ability of the material to the deformation caused by the loading and the geometrical influence of the structure on the dynamic response. For an impulsively loaded beam or plate, the final dimensionless deflection is solely dependent upon the response number. When the secondary effects of finite deflections, strain-rate sensitivity or transverse shear are taken into account, the response number is as useful as in the case of simple bending theory. Finally, the number is not only suitable to idealized dynamic loads but also applicable to dynamic loads of general shape.

Towards an Understanding of the Influence of Sedimentation on Colloidal Aggregation by Peclet Number

The Peclet number is a useful index to estimate the importance of sedimentation as compared to the Brownian motion. However, how to choose the characteristic length scale for the Peclet number evaluation is rather critical because the diffusion length increases as the square root of the time whereas the drifting length is linearly related to time. Our Brownian dynamics simulation shows that the degree of sedimentation influence on the coagulation decreases when the dispersion volume fraction increases. Therefore using a fixed length, such as the diameter of particle, as the characteristic length scale for Peclet number evaluation is not a good choice when dealing with the influence of sedimentation on coagulation. The simulations demonstrated that environmental factors in the coagulation process, such as dispersion volume fraction and size distribution, should be taken into account for more reasonable evaluation of the sedimentation influence.

Instability from steady and axisymmetric to steady and asymmetric floating half zone convection in a fat liquid bridge of larger Prandtl number

The linear instability analysis of the present paper shows that the thermocapillary convection in a half floating zone of larger Prandtl number has a steady instability mode w(i) = 0 and m = 1 for a fat liquid bridge V = 1.2 with small geometrical aspect ratio A = 0.6. This conclusion is different from the usual idea of hydrothermal instability, and implies that the instability of the system may excite a steady and axial asymmetric state before the onset of oscillation in the ease of large Prandtl number.

Prediction of structural dynamic plastic shear failure by Johnson's damage number

It is proved that Johnson's damage number is the sole similarity parameter for dynamic plastic shear failure of structures loaded impulsively, therefore, dynamic plastic shear failure can be understood when damage number reaches a critical value. It is suggested that the damage number be generally used to predict the dynamic plastic shear failure of structures under various kinds of dynamic loads (impulsive loading, rectangular pressure pulse, exponential pressure pulse, etc.,). One of the advantages for using the damage number to predict such kind of failure is that it is conveniently used for dissimilar material modeling.