The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
P-sequences are used for coding binary trees and they are also an alternative representation for well-formed parentheses strings. We present here the first Gray code and loopless generating algorithm for P-sequences, and extend them in a Gray code and a new loopless generating algorithm for well-formed parentheses strings. Ranking and unranking algorithms are also discussed.
Convex polygons in the plane can be defined explicitly as an ordered list of vertices, or given implicitly, for example by a list of linear constraints. The latter representation has been considered in several fields such as facility location, robotics and computer graphics. In this paper, we investigate many fundamental geometric problems for implicitly represented polygons and give simple and fast...
Given a configuration C of geometric objects in R2 (called the input configuration), a target configurationT of geometric objects in R1, and a class S of allowable sectioning lines we consider in this paper many variations on the following problem: ‘Is there a line S∈S such that the section S∩C is equivalent by rigid motion to the target T?’
We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m−3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m−1 preemptions. This is better...
In this paper we present an Ω(nlog n) lower bound proof for several covering problems including the optimal line bipartition problem, min-max covering by two axis parallel rectangles, discrete and continuous two-center problems, two-line center problem, etc. Our proofs are based on using the ‘rotational reduce technique’ and well-known lower bound for the maximal gap problem.
The issue of avoiding deadlocks in unmanned automated manufacturing systems with automated guided vehicle systems is addressed in this paper. In the automated guided vehicle systems, multi-load vehicles are used. A simple and easily adoptable deadlock-free real-time vehicle control strategy is developed for this type of vehicle, by using an intelligent rule-based method. The proposed strategy uses...
The basic Vehicle Routing Problem (VRP) consists of computing a set of trips of minimum total cost, to deliver fixed amounts of goods to customers with a fleet of identical vehicles. Few papers address the case with several types of vehicles (heterogeneous fleet). Most of them assume an unlimited number of vehicles of each type, to dimension the fleet from a strategic point of view. This paper tackles...
In this paper, we consider a flow-line manufacturing system organized as a series of workstations separated by finite buffers. The failure and repair times of machines are supposed to be exponentially distributed. The production rate of each machine is deterministic, and different machines may have different production rates. The buffer allocation problem consists in determining the buffer capacities...
Multifunction radar has to perform several types of tasks. Some of them are systematic: the case of probing and guidance tasks. Others are random: the case when a new object is detected in the sky and should be confirmed and tracked. The tasks that consist of tracking targets are also random, since these targets may follow unexpected trajectories, possibly asking for a search in the neighborhood of...
A new class of explicit approximate inverse preconditioning is introduced for solving fourth-order equations, based on the ‘coupled equation approach’, by the domain decomposition method in conjunction with various finite difference approximation schemes. Explicit approximate inverse arrow-type matrix techniques, based on the concept of sparse LU-type factorization procedures, are introduced for...
Although a large number of performance evaluation tools are available today, the efficient performance prediction of a multicomputer system remains a difficult task. In this work, the development of a system capable of predicting the timings for an application executed on the multicomputer Parsytec GCel3/512 is investigated.
The Fast Fourier Transform (FFT) was named one of the Top Ten algorithms of the 20th century , and continues to be a focus of current research. A problem with currently used FFT packages is that they require large, finely tuned, machine specific libraries, produced by highly skilled software developers. Therefore, these packages fail to perform well across a variety of architectures. Furthermore,...
The High Performance Fortran (HPF) language and the Message Passing Interface (MPI) are two widely used methods to achieve parallelism on today's clusters and multiprocessor supercomputers. HPF is a distinct language providing extensions to Fortran 90/95 to express parallel execution paths and regions. MPI is a library of communication calls that can be inserted into modern high-level languages (C...
In this paper, fast evaluation of Fourier integrals using additive and dual additive algorithms are considered. For this, we introduce formulas for fast computing Fourier integrals and we present possible variants of structural realization of spectral analyzer. Computer simulation of additive algorithms for solving differential equations is described. The algorithms presented in this paper are suitable...
Parallel complexity results for designing banded triangular solvers are provided. In particular, several lower bounds based on data layout and communication along a ring are derived based on solving such systems using substitution. Lastly, a near-optimal solver for a ring is discussed and provided.
Let [a,b] be a line segment with end points a, b and ν a point at which a viewer is located, all in R3. The aperture angle of [a,b] from point ν, denoted by θ(ν), is the interior angle at ν of the triangle Δ(a,b,ν). Given a convex polyhedron P not intersecting a given segment [a,b] we consider the problem of computing θmax(ν) and θmin(ν), the maximum and minimum values of θ(ν) as ν varies over all...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.