On Shank's algorithm for modular square roots.
On the behaviour of learning algorithms in a changing environment with application to data network routing problem
On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra.
On the distributed decision-making complexity of the minimum vertex cover problem
On the parallel complexity of the alternating hamiltonian cycle problem
On the parallel complexity of the alternating Hamiltonian cycle problem
Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...
On the proper intervalization of colored caterpillar trees
This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For...
On-line computations of the ideal lattice of posets
On-line evaluation of powers using Euclid's algorithm
On-line -adic covering by the method of the -th segment and its application to on-line covering by cubes.
Optimal sequential and parallel algorithms for cut vertices and bridges on trapezoid graphs.