A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.

The ballast pick-up problem. A theoretical approach and two experimental campaigns

The aim of this contribution is to present a theoretical approach and two experimental campaigns (on wind tunnel and on the track) concerning the research work about the ballast train-induced-wind erosion (BTIWE) phenomenon. When a high speed train overpasses the critical speed, it produces a wind speed close to the track large enough to start the motion of the ballast elements, eventually leading to the rolling of the stones (Kwon and Park, 2006) and, if these stones get enough energy, they can jump and then initiate a saltation-like chain reaction, as found in the saltation processes of soil eolian erosion (Bagnold, 1941). The expelled stones can reach a height which is larger than the lowest parts of the train, striking them (and the track surroundings) producing considerable damage that should be avoided. There is not much published work about this phenomenon, in spite of the great interest that exists due to its relevant applications in increasing the maximum operative train speed. Particularly, the initiation of flight of ballast due to the pass of a high speed train has been studied by Kwon and Park (2006) by performing field and wind tunnel experiments.