Calcul des idéaux d'un ordonné fini
Canonical greedy algorithms and dynamic programming
Chance constrained bottleneck transportation problem with preference of routes
This paper considers a variant of the bottleneck transportation problem. For each supply-demand point pair, the transportation time is an independent random variable. Preference of each route is attached. Our model has two criteria, namely: minimize the transportation time target subject to a chance constraint and maximize the minimal preference among the used routes. Since usually a transportation pattern optimizing two objectives simultaneously does not exist, we define non-domination in this...
Chemins extrémaux d'un graphe doublement valué
Clique partitioning of interval graphs with submodular costs on the cliques
Given a graph G = (V,E) and a “cost function” (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where G is an interval graph and f belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the...
Comment construire un graphe PERT minimal
Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
Comparison of algorithms in graph partitioning
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
Comparison of algorithms in graph partitioning
We first describe four recent methods to cluster vertices of an undirected non weighted connected graph. They are all based on very different principles. The fifth is a combination of classical ideas in optimization applied to graph partitioning. We compare these methods according to their ability to recover classes initially introduced in random graphs with more edges within the classes than between them.
Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
Computational experiments with some approximation algorithms for the travelling salesman problem