Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

Influence of Surface Texture and Roughness of Softer and Harder Counter Materials on Friction During Sliding

Surface texture influences friction during sliding contact conditions. In the present investigation, the effect of surface texture and roughness of softer and harder counter materials on friction during sliding was analyzed using an inclined scratch testing system. In the experiments, two test configurations, namely (a) steel balls against aluminum alloy flats of different surface textures and (b) aluminum alloy pins against steel flats of different surface textures, are utilized. The surface textures were classified into unidirectionally ground, 8-ground, and randomly polished. For a given texture, the roughness of the flat surfaces was varied using grinding or polishing methods. Optical profilometer and scanning electron microscope were used to characterize the contact surfaces before and after the experiments. Experimental results showed that the surface textures of both harder and softer materials are important in controlling the frictional behavior. The softer material surface textures showed larger variations in friction between ground and polished surfaces. However, the harder material surface textures demonstrated a better control over friction among the ground surfaces. Although the effect of roughness on friction was less significant when compared to textures, the harder material roughness showed better correlations when compared to the softer material roughness.

Effect Of Directionality Of Grinding Marks On Friction And Formation Of Transfer Layer

Surface texture influences friction and transfer layer formation during sliding. In the present investigation, basic studies were conducted using inclined pin-on-plate sliding tester to understand the effect of directionality of surface grinding marks of hard material on friction and transfer layer formation during sliding against soft materials. 080 M40 steel plates were ground to attain different surface roughness with unidirectional grinding marks. Then pins made of soft materials such as pure Al, pure Mg and Al-Mg alloy were slid against the prepared steel plates. Grinding angle (i.e., the angle between direction of sliding and grinding marks) was varied between 0 degrees and 90 degrees in the tests. Experiments were conducted under both dry and lubricated conditions on each plate in ambient environment. It was observed that the transfer layer formation and the coefficient of friction, which has two components adhesion and plowing - depend primarily on the directionality of grinding marks of the harder mating surface, and independent of surface roughness of the harder mating surface. For the case of pure Mg, stick-slip phenomenon was observed under dry condition for all grinding angles and it was absent upto 20 degrees grinding angles under lubricated condition. However, for the case of Al, it was observed only under lubricated conditions for angles exceeding 20 degrees. As regards the alloy, namely, Al-Mg alloy, it, was absent in both conditions. For the case of pure Mg and Al, it was observed that the amplitude of stick-slip motion primarily depends on plowing component of friction. The grinding angle effect on coefficient of friction was attributed to the variation of plowing component of friction with grinding angle.

Correlating The Features Of Topography To Friction By Sliding Experiments

Friction can influence the quality of the finished product to a large extent in certain manufacturing processes. Sheet metal forming is a particular case, where the friction between the hard-die and the relatively soft work-piece can be extremely important. Under such conditions, topography of the harder surface can influence the resistance to traction at the interface. This paper discusses about the correlation between certain features of the surface; topography and coefficient of friction based on experiments involving sliding of a few soft metal pins against a harder material. A brief description of the experimental procedure and the analysis are presented. A hybrid parameter which encapsulates both the amplitude features as well as the relative packing of peaks is shown to correlate well with the coefficient of friction.

Evolution of cooperation by reciprocation within structured demes

The iterative two-person Prisoners’ Dilemma game has been generalised to theN-person case. The evolution of cooperation is explored by matching the Tit For Tat (TFT) strategy (Axelrod and Hamilton 1981) against the selfish strategy. Extension of TFT toN-person situations yields a graded set of strategies from the softest TFT, which continues cooperation even if only one of the opponents reciprocates it, to the hardest, which would do so only when all the remaining opponents cooperate. The hardest TFT can go to fixation against the selfish strategy provided it crosses a threshold frequencypc. All the other TFT are invadable by the selfish (D) or the pure defector strategy, while none can invadeD. Yet, provided a thresholdpc is crossed, they can coexist stably withD. AsN, the size of the group increases, the threshold pc also increases, indicating that the evolution of cooperation is more difficult for larger groups. Under certain conditions, only the soft TFT can coexist stably against the selfish strategyD, while the harder ones cannot. An interesting possibility of a complete takeover of the selfish population by successive invasions by harder and harder TFT strategies is also presented.

Investigation of the local Fe magnetic moments at the grain boundaries of the Ca2FeReO6 double perovskite

The local Fe ferromagnetic (FM) moment at the grain boundaries of a ceramic sample of Ca2FeReO6 double perovskite was investigated by means of x-ray magnetic circular dichroism spectroscopy at the Fe L-2,L-3 edges and compared to the overall bulk magnetization. We found that, at the grain boundaries, the Fe FM moments at H=5 T are much smaller than expected and that the MxH curve is harder than in the bulk magnetization. These results suggest a larger degree of Fe/Re antisite disorder at the grain boundaries of this sample, shedding light into the intriguing nonmetallic resistivity behavior despite the reported presence of free carriers. (c) 2007 American Institute of Physics.

Influence of surface texture and roughness parameters on friction and transfer layer formation during sliding of aluminium pin on steel plate

Surface texture of harder mating surfaces plays an important role during sliding against softer materials and hence the importance of characterizing the surfaces in terms of roughness parameters. In the present investigation, basic studies were conducted using inclined pin-on-plate sliding tester to understand the surface texture effect of hard surfaces on coefficient of friction and transfer layer formation. A tribological couple made of a super purity aluminium pin against steel plate was used in the tests. Two surface parameters of steel plates, namely roughness and texture, were varied in the tests. It was observed that the transfer layer formation and the coefficient of friction along with its two components, namely, the adhesion and plowing, are controlled by the surface texture and are independent of surface roughness (R-a). Among the various surface roughness parameters, the average or the mean slope of the profile was found to explain the variations best. Under lubricated conditions, stick-slip phenomena was observed, the amplitude of which depends on the plowing component of friction. The presence of stick-slip motion under lubricated conditions could be attributed to the molecular deformation of the lubricant component confined between asperities. (C) 2009 Elsevier B. V. All rights reserved.

Influence of tilt angle of plate on friction and transfer layer—A study of aluminium pin sliding against steel plate

In the present investigation, unidirectional grinding marks were attained on the steel plates. Then aluminium (Al) pins were slid at 0.2°, 0.6°, 1.0°, 1.4°, 1.8°, 2.2° and 2.6° tilt angles of the plate with the grinding marks perpendicular and parallel to the sliding direction under both dry and lubricated conditions using a pin-on-plate inclined sliding tester to understand the influence of tilt angle and grinding marks direction of the plate on coefficient of friction and transfer layer formation. It was observed that the transfer layer formation and the coefficient of friction depend primarily on the grinding marks direction of the harder mating surface. Stick-slip phenomenon was observed only under lubricated conditions. For the case of pins slid perpendicular to the unidirectional grinding marks stick-slip phenomenon was observed for tilt angles exceeding 0.6°, the amplitude of which increases with increasing tilt angles. However, for the case of the pins slid parallel to the unidirectional grinding marks the stick-slip phenomena was observed for angles exceeding 2.2°, the amplitude of which also increases with increasing tilt angle. The presence of stick-slip phenomena under lubricated conditions could be attributed to the molecular deformation of the lubricant component confined between asperities.

Effect of directionality of unidirectional grinding marks on friction and transfer layer formation of Mg on steel using inclined scratch test

Surface topography has been known to play an important role in the friction and transfer layer formation during sliding. In the present investigation, EN8 steel flats were ground to attain different surface roughness with unidirectional grinding marks. Pure Mg pins were scratched on these surfaces using an Inclined Scratch Tester to study the influence of directionality of surface grinding marks on coefficient of friction and transfer layer formation. Grinding angle (i.e., the angle between direction of scratch and grinding marks) was varied between 0 degrees and 90 degrees during the tests. Experiments were conducted under both dry and lubricated conditions. Scanning electron micrographs of the contact surfaces of pins and flats were used to reveal the surface features that included the morphology of the transfer layer. It was observed that the average coefficient of friction and transfer layer formation depend primarily on the directionality of the grinding marks but were independent of surface roughness on the harder mating surface. In addition, a stick-slip phenomenon was observed, the amplitude of which depended both on the directionality of grinding marks and the surface roughness of the harder mating surface. The grinding angle effect on the coefficient of friction, which consists of adhesion and plowing components, was attributed to the variation of plowing component of friction. (c) 2006 Elsevier B.V. All rights reserved.

Max-Coloring Paths: Tight Bounds and Extensions

The max-coloring problem is to compute a legal coloring of the vertices of a graph G = (V, E) with a non-negative weight function w on V such that Sigma(k)(i=1) max(v epsilon Ci) w(v(i)) is minimized, where C-1, ... , C-k are the various color classes. Max-coloring general graphs is as hard as the classical vertex coloring problem, a special case where vertices have unit weight. In fact, in some cases it can even be harder: for example, no polynomial time algorithm is known for max-coloring trees. In this paper we consider the problem of max-coloring paths and its generalization, max-coloring abroad class of trees and show it can be solved in time O(vertical bar V vertical bar+time for sorting the vertex weights). When vertex weights belong to R, we show a matching lower bound of Omega(vertical bar V vertical bar log vertical bar V vertical bar) in the algebraic computation tree model.

Influence of Die Surface Textures during Metal Forming-A Study Using Experiments and Simulation

Friction plays an important role in metal forming processes, and the surface texture of the die is a major factor that influences friction. In the present investigation, experiments were conducted to understand the role of surface texture of the harder die surface and load on coefficient of friction. The data analysis showed that the coefficient of friction is highly dependent on the surface texture of the die surface. Assigning different magnitude of coefficients of friction, obtained in the experiments, at different regions between the die and the workpiece, Finite element (FE) simulation of a compression test was carried out to understand the effect of friction on deformation and stress/strain-rate distribution. Simulation results revealed that, owing to the difference in coefficient of friction, there is a change in metal flow pattern. Both experimental and simulation results confirmed that the surface texture of the die surface and thus coefficient of friction directly affects the strain rate and flow pattern of the workpiece.

A delta13C record of late Quaternary climate change from tropical peats in southern India

STABLE-ISOTOPE ratios of carbon in soils or lake sediments1-3 and of oxygen and hydrogen in peats4,5 have been found to reflect past moisture variations and hence to provide valuable palaeoclimate records. Previous applications of the technique to peat have been restricted to temperate regions, largely because tropical climate variations are less pronounced, making them harder to resolve. Here we present a deltaC-13 record spanning the past 20 kyr from peats in the Nilgiri hills, southern India. Because the site is at high altitude (>2,000 m above sea level), it is possible to resolve a clear climate signal. We observe the key climate shifts that are already known to have occurred during the last glacial maximum (18 kyr ago) and the subsequent deglaciation. In addition, we observe an arid phase from 6 to 3.5 kyr ago, and a short, wet phase about 600 years ago. The latter appears to correspond to the Mediaeval Warm Period, which previously was believed to be confined to Europe and North America6,7. Our results therefore suggest that this event may have extended over the entire Northern Hemisphere.

Role of Surface Texture, Roughness, and Hardness on Friction During Unidirectional Sliding

In the present investigation, experiments were conducted by unidirectional sliding of pins made of FCC metals (Pb, Al, and Cu) with significantly different hardness values against the steel plates of various surface textures and roughness using an inclined pin-on-plate sliding apparatus in ambient conditions under both the dry and lubricated conditions. For a given material pair, it was observed that transfer layer formation and the coefficient of friction along with its two components, namely adhesion and plowing, are controlled by the surface texture of the harder mating surfaces and are less dependent of surface roughness (R (a)) of the harder mating surfaces. The effect of surface texture on the friction was attributed to the variation of the plowing component of friction for different surfaces. It was also observed that the variation of plowing friction as a function of hardness depends on surface textures. More specifically, the plowing friction varies with hardness of the soft materials for a given type of surface texture and it is independent of hardness of soft materials for other type of surface texture. These variations could be attributed to the extent of plane strain conditions taking place at the asperity level during sliding. It was also observed that among the surface roughness parameters, the mean slope of the profile, Delta (a), correlated best with the friction. Furthermore, dimensionless quantifiable roughness parameters were formulated to describe the degree of plowing taking place at the asperity level.

Correction for Bias in Downscaling GCM Simulations for Hydrologic Impact Assessment

In a statistical downscaling model, it is important to remove the bias of General Circulations Model (GCM) outputs resulting from various assumptions about the geophysical processes. One conventional method for correcting such bias is standardisation, which is used prior to statistical downscaling to reduce systematic bias in the mean and variances of GCM predictors relative to the observations or National Centre for Environmental Prediction/ National Centre for Atmospheric Research (NCEP/NCAR) reanalysis data. A major drawback of standardisation is that it may reduce the bias in the mean and variance of the predictor variable but it is much harder to accommodate the bias in large-scale patterns of atmospheric circulation in GCMs (e.g. shifts in the dominant storm track relative to observed data) or unrealistic inter-variable relationships. While predicting hydrologic scenarios, such uncorrected bias should be taken care of; otherwise it will propagate in the computations for subsequent years. A statistical method based on equi-probability transformation is applied in this study after downscaling, to remove the bias from the predicted hydrologic variable relative to the observed hydrologic variable for a baseline period. The model is applied in prediction of monsoon stream flow of Mahanadi River in India, from GCM generated large scale climatological data.

Response of Materials during sliding on various surface textures

In the present investigation, basic studies were conducted using Inclined pin-on-plate sliding Tester to understand the role of surface texture of hard material against soft materials during sliding. Soft materials such as Al-Mg alloy, pure Al and pure Mg were used as pins and 080 M40 steel was used as plate in the tests. Two surface parameters of steel plates — roughness and texture — were varied in tests. It was observed that the transfer layer formation and the coefficient of friction which has two components, namely adhesion and plowing component, are controlled by the surface texture of harder material. For the case of Al-Mg alloy, stick-slip phenomenon was absent under both dry and lubricated conditions. However, for the case of Al, it was observed only under lubricated conditions while for the case of Mg, it was observed under both dry and lubricated conditions. Further, it was observed that the amplitude of stick-slip motion primarily depends on plowing component of friction. The plowing component of friction was highest for the surface that promotes plane strain conditions near the surface and was lowest for the surface that promotes plane stress conditions near the surface.