Posts classified under: Séminaire Algo

La notion de structure transparaît dans de nombreux domaines scientifiques comme une approche pragmatique pour capturer le fait que des objets complexes peuvent être décomposés en éléments plus simples. Nous proposons une formalisation de cette notion et montrons comment s'en servir pour unifier diverses variations des diagrammes de décision binaires (BDD, une représentation simple, pragmatique, … Continue reading Séminaire Algorithmique : « Introduction à la théorie des structures et son application aux fonctions Booléennes », Joan Thibault (IRISA, Rennes)

In this talk, we will explore graphs of shortest paths—directed acyclic graphs (DAGs) derived from shortest path traversals of a graph rooted at a fixed source. After establishing a precise definition of these structures, we will examine methods for uniformly sampling them and investigate their typical shape. Along the way, we will uncover interesting connections … Continue reading Séminaire Algorithmique : « Graphs of Shortest Paths », Mehdi Naima (LIP6, Sorbonne Univ.)

The domatic number of a graph G is the maximum number of pairwise disjoint dominating sets of G. We are interested in the LP-relaxation of this parameter, which is called the fractional domatic number of G. We study its extremal value in the class of graphs of minimum degree d. The fractional domatic number of … Continue reading Séminaire Algorithmique : « Fractional domatic number and minimum degree », Hugo Demaret (Ecole Polytechnique et GREYC)