51 research outputs found
Parameterized Algorithms and Data Reduction for Safe Convoy Routing
No full textWe study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph G=(V,E), two vertices s,t in V, and two integers k,l, we search for a simple s-t-path with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2^O(tw) * l^2 * n-time algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph
MEP: a 3D PIC Code for the Simulation of the Dynamics of a Non-Neutral Plasma
No full textThe three-dimensional evolution of a pure electron plasma is studied by means of a newly developed particle-in-cell code which solves the drift-Poisson system where kinetic effects in the motion parallel to the magnetic field are taken into account. Different results relevant to the non-linear dynamics of trapped plasmas and low-energy electron beams are presented. [All rights reserved Elsevier]
Experimental investigation of coherent structures in a low-energy electron beam
No full textA sharp transition to a space-charge dominated regime is induced in a low-energy electron beam produced in a Malmberg–Penning trap by increasing the emission current of the source. The transition is characterized by the appearance of a region, around the axis of the beam, not accessible to beam electrons, and by the fast development of coherent structures in the remaining electron plasma, due to the sharp increase of local vorticity. The results are interpreted in the framework of a cold fluid drift–Poisson model, and using a three-dimensional particle-in-cell simulation code
On Modification of an Asymptotically Optimal Algorithm for the Maximum Euclidean Traveling Salesman Problem
No full text
An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution
No full text- …
