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.

Quantitative evaluation of artifact removal in real magnetoencephalogram signals with blind source separation

The magnetoencephalogram (MEG) is contaminated with undesired signals, which are called artifacts. Some of the most important ones are the cardiac and the ocular artifacts (CA and OA, respectively), and the power line noise (PLN). Blind source separation (BSS) has been used to reduce the influence of the artifacts in the data. There is a plethora of BSS-based artifact removal approaches, but few comparative analyses. In this study, MEG background activity from 26 subjects was processed with five widespread BSS (AMUSE, SOBI, JADE, extended Infomax, and FastICA) and one constrained BSS (cBSS) techniques. Then, the ability of several combinations of BSS algorithm, epoch length, and artifact detection metric to automatically reduce the CA, OA, and PLN were quantified with objective criteria. The results pinpointed to cBSS as a very suitable approach to remove the CA. Additionally, a combination of AMUSE or SOBI and artifact detection metrics based on entropy or power criteria decreased the OA. Finally, the PLN was reduced by means of a spectral metric. These findings confirm the utility of BSS to help in the artifact removal for MEG background activity.

Two-dimensional plasma expansion in a magnetic nozzle: Separation due to electron inertia

A previous axisymmetric model of the supersonic expansion of a collisionless, hot plasma in a divergent magnetic nozzle is extended here in order to include electron-inertia effects. Up to dominant order on all components of the electron velocity, electron momentum equations still reduce to three conservation laws. Electron inertia leads to outward electron separation from the magnetic streamtubes. The progressive plasma filling of the adjacent vacuum region is consistent with electron-inertia being part of finite electron Larmor radius effects, which increase downstream and eventually demagnetize the plasma. Current ambipolarity is not fulfilled and ion separation can be either outwards or inwards of magnetic streamtubes, depending on their magnetization. Electron separation penalizes slightly the plume efficiency and is larger for plasma beams injected with large pressure gradients. An alternative nonzero electron-inertia model [E. Hooper, J. Propul. Power 9, 757 (1993)] based on cold plasmas and current ambipolarity, which predicts inwards electron separation, is discussed critically. A possible competition of the gyroviscous force with electron-inertia effects is commented briefly.

Solving the minimum vertex floodlight problem with hybrid metaheuristics

In this paper we propose four approximation algorithms (metaheuristic based), for the Minimum Vertex Floodlight Set problem. Urrutia et al. [9] solved the combinatorial problem, although it is strongly believed that the algorithmic problem is NP-hard. We conclude that, on average, the minimum number of vertex floodlights needed to illuminate a orthogonal polygon with n vertices is n/4,29.

Induced shock loads during the separation of the Ariane 5 VEB structure

Tests used to simulate the separation of the lower stage of the Ariane Vehicle Equipment Bay (VEB) were carried out on a flat full scale model. Theoretical studies carried out prior to testing are described. Three different mathematical methods, finite element, component element, and wave propagation, were used. Comparison of the predicted theoretical results with the actual test results is planned.