A Left-First Search Algorithm for Planar Graphs.
A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs
ACM Computing Classification System (1998): G.2.2.We propose an algorithm that computes the length of a longest path in a cactus graph. Our algorithm can easily be modified to output a longest path as well or to solve the problem on cacti with edge or vertex weights. The algorithm works on rooted cacti and assigns to each vertex a two-number label, the first number being the desired parameter of the subcactus rooted at that vertex. The algorithm applies the divide-and-conquer approach and computes...
A local limit theorem with speed of convergence for euclidean algorithms and diophantine costs
For large N, we consider the ordinary continued fraction of x=p/q with 1≤p≤q≤N, or, equivalently, Euclid’s gcd algorithm for two integers 1≤p≤q≤N, putting the uniform distribution on the set of p and qs. We study the distribution of the total cost of execution of the algorithm for an additive cost function c on the set ℤ+* of possible digits, asymptotically for N→∞. If c is nonlattice and satisfies mild growth conditions, the local limit theorem was proved previously by the second named author....
A Macsyma implementation of Zeilberger's fast algorithm.
A multicriteria genetic tuning for fuzzy logic controllers.
This paper presents the use of genetic algorithms to develop smartly tuned fuzzy logic controllers in multicriteria complex problems. This tuning approach has some specific restrictions that make it very particular and complex because of the large time requirements existing due to the need of considering multiple criteria -which enlarges the solution search space-, and to the long computation time models usually used for fitness assessment. To solve these restrictions, two efficient genetic tuning...
A multilevel algorithm for the minimum 2-sum problem.
A new algorithm for finding minimal cycle-breaking sets of turns in a graph.
A new algorithm for the available transfer capability determination.
A new evolutionary optimization technique.
A new interpretor for PARI/GP
When Henri Cohen and his coworkers set out to write PARI twenty years ago, GP was an afterthought. While GP has become the most commonly used interface to the PARI library by a large margin, both the gp interpretor and the GP language are primitive in design. Paradoxically, while gp allows to handle very high-level objects, GP itself is a low-level language coming straight from the seventies.We rewrote GP as a compiler/evaluator pair, implementing several high-level features (statically scoped variables,...
A New Method for Computing Polynomial Greatest Common Divisors and Polynomial Remainder Sequences.
A new possibility in bi-directional search
A new practical linear space algorithm for the longest common subsequence problem
This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths and , , on an alphabet of size , we first present an algorithm which determines the length of an LCS in time and space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in time while preserving the linear space bound, thus solving...
A new search model for evolutionary algorithms.
A non-deteministic time hierarchy over the reals.
A Non-Recursive Algorithm for Polygon Triangulation
A note concerning the limit distribution of the quicksort algorithm
A note on a two dimensional knapsack problem with unloading constraints
In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1,...,C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation...
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity , and items of different classes, each item with class and size . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size . In...
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size...