Quasi-Optimal Range Searching in Spaces of Finite VC-Dimension.
Quelques aspects du problème
Quelques problèmes d'informatique
Random generation for finitely ambiguous context-free languages
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
Random Generation for Finitely Ambiguous Context-free Languages
We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O(n2 log n) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1-NAuxPDA with polynomially bounded ambiguity.
Random -sat: the limiting probability for satisfiability for moderately growing .
Range Searching with Efficient Hierarchical Cuttings.
Real-time and complexity problems in automata theory
Recent results and open problems in analytic computational complexity
Reconstruction of complete interval tournaments. II.
Recouvrement et partition en chaînes des arêtes d'un graphe cubique
Rectilinear Shortest Paths in the Presence of Rectangular Barriers.
Relative bilinear complexity and matrix multiplication.
Satisfiability and computing van der Waerden numbers.
Selected multicriteria shortest path problems: an analysis of complexity, models and adaptation of standard algorithms
The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multi-objective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness...
Self-reducibility structures and solutions of NP problems.
Using polynomial time self-reducibility structures, we characterize certain helping notions, show how the characterization provides the main tool for the proof of known relationships between decisional and functional NP-complete problems, and extend this relationships to the case of optimization NP-complete problems.
Semi-algebraic complexity-additive complexity of diagonalization of quadratic forms.
We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....
Separating Two Simple Polygons by a Sequence of Translations.
Several methods of the reduction of computational complexity.
Shortest Watchman Routes in Simple Polygons.