Un algorithme efficace pour un arbre de classifications
Un algorithme efficace recherchant l'isomorphisme de 2 graphes
Un algorithme heuristique de décomposition d'un graphe
Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée
Nous présentons une méthode de Séparation et Évaluation Progressive pour la bipartition d’un graphe en 2 sous-ensembles ayant une cardinalité fixée. À chaque nœud de l’arbre de recherche, nous calculons une borne inférieure en dualisant les contraintes d’intégralité et en approximant le domaine réalisable par un ellipsoïde. Une borne supérieure est également calculée par la méthode Tabou. Des résultats numériques sont présentés et commentés.
Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée
A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.
Un algorithme pour l'obtention d'une chaîne Hamiltonienne en partant de l'arbre minimal d'un graphe
Un algorithme pour pallier l'effet Condorcet
Un nouveau type de preuve mathématique : le théorème des quatre couleurs. I - Exposé préliminaire
Un nouveau type de preuve mathématiques : II - Le théorème des quatre couleurs
Un principe variationnel pour les empilements de cercles.
Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire
Unavoidable set of face types for planar maps
The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.
Unbalanced unicyclic and bicyclic graphs with extremal spectral radius
A signed graph is a graph whose edges are labeled by signs. If has vertices, its spectral radius is the number , where are the eigenvalues of the signed adjacency matrix . Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes and of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.
Underlying Graphs of 3-Quasi-Transitive Digraphs and 3-Transitive Digraphs
A digraph is 3-quasi-transitive (resp. 3-transitive), if for any path x0x1 x2x3 of length 3, x0 and x3 are adjacent (resp. x0 dominates x3). C´esar Hern´andez-Cruz conjectured that if D is a 3-quasi-transitive digraph, then the underlying graph of D, UG(D), admits a 3-transitive orientation. In this paper, we shall prove that the conjecture is true.
Undirected and directed graphs with near polynomial growth
The growth function of a graph with respect to a vertex is near polynomial if there exists a polynomial bounding it above for infinitely many positive integers. In the paper vertex-symmetric undirected graphs and vertex-symmetric directed graphs with coinciding in- and out-degrees are described in the case their growth functions are near polynomial.
Undirected strict gammoids
Une approche métrique de la rétraction dans les ensembles ordonnés et les graphes
Une construction du groupe de Fischer
Une heuristique pour le problème de l'arbre de Steiner