Pressure Dependence of Glass Transition in As2Te3 Glass

Amorphous solids prepared from their melt state exhibit glass transition phenomenon upon heating. Viscosity, specific heat, and thermal expansion coefficient of the amorphous solids show rapid changes at the glass transition temperature (T-g). Generally, application of high pressure increases the T-g and this increase (a positive dT(g)/dP) has been understood adequately with free volume and entropy models which are purely thermodynamic in origin. In this study, the electrical resistivity of semiconducting As2Te3 glass at high pressures as a function of temperature has been measured in a Bridgman anvil apparatus. Electrical resistivity showed a pronounced change at T-g. The T-g estimated from the slope change in the resistivity-temperature plot shows a decreasing trend (negative dT(g)/dP). The dT(g)/dP was found to be -2.36 degrees C/kbar for a linear fit and -2.99 degrees C/kbar for a polynomial fit in the pressure range 1 bar to 9 kbar. Chalcogenide glasses like Se, As2Se3, and As30Se30Te40 show a positive dT(g)/dP which is very well understood in terms of the thermodynamic models. The negative dT(g)/dP (which is generally uncommon in liquids) observed for As2Te3 glass is against the predictions of the thermodynamic models. The Adam-Gibbs model of viscosity suggests a direct relationship between the isothermal pressure derivative of viscosity and the relaxational expansion coefficient. When the sign of the thermal expansion coefficient is negative, dT(g)/dP = Delta k/Delta alpha will be less than zero, which can result in a negative dT(g)/dP. In general, chalcogenides rich in tellurium show a negative thermal expansion coefficient (NTE) in the supercooled and stable liquid states. Hence, the negative dT(g)/dP observed in this study can be understood on the basis of the Adams-Gibbs model. An electronic model proposed by deNeufville and Rockstad finds a linear relation between T-g and the optical band gap (E-g for covalent semiconducting glasses when they are grouped according to their average coordination number. The electrical band gap (Delta E) of As2Te3 glass decreases with pressure. The optical and electrical band gaps are related as Delta E-g = 2 Delta E; thus, a negative dT(g)/dP is expected when As2Te3 glass is subjected to high pressures. In this sense, As2Te3 is a unique glass where its variation of T-g with pressure can be understood by both electronic and thermodynamic models.

A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis

In this paper, we study a problem of designing a multi-hop wireless network for interconnecting sensors (hereafter called source nodes) to a Base Station (BS), by deploying a minimum number of relay nodes at a subset of given potential locations, while meeting a quality of service (QoS) objective specified as a hop count bound for paths from the sources to the BS. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard. For this problem, we propose a polynomial time approximation algorithm based on iteratively constructing shortest path trees and heuristically pruning away the relay nodes used until the hop count bound is violated. Results show that the algorithm performs efficiently in various randomly generated network scenarios; in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay. We then use random graph techniques to obtain, under a certain stochastic setting, an upper bound on the average case approximation ratio of a class of algorithms (including the proposed algorithm) for this problem as a function of the number of source nodes, and the hop count bound. To the best of our knowledge, the average case analysis is the first of its kind in the relay placement literature. Since the design is based on a light traffic model, we also provide simulation results (using models for the IEEE 802.15.4 physical layer and medium access control) to assess the traffic levels up to which the QoS objectives continue to be met. (C) 2014 Elsevier B.V. All rights reserved.

UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.