Eliminating more than vertices in graphs
summary: Considérons le jeu suivant sur un graphe. À chaque tour, le joueur peut enlever un sommet de chaque composante connexe du graphe courant. Le but du jeu est d’éliminer tous les sommets du graphe. Le nombre minimum de tours nécessaires est appelé la treedepth du graphe. C’est ...
Reconstruction de graphes via des requêtes sur les triplets
summary: Considérons un oracle disposant d'un graphe labellisé caché. L'objectif de la reconstruction de graphes est de retrouver ce graphe caché en interrogeant l'oracle avec certains types de requêtes. Les requêtes que nous examinons portent sur des triplets de sommets du graphe, plus précisément, sur la structure ...
Fractional domatic number and minimum degree
summary: We present a study of a graph parameter in graph theory, named the fractional domatic number. A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set. The domatic number of a graph is ...
Travo: a classroom open source Python toolkit
summary: Teaching computer science or computational courses inevitably implies collaboration on code. Software forges can provide helpful infrastructure to support and improve collaboration in teaching workflows. This talk will present Travo, an open source Python toolkit turning your favorite forge into a flexible management solution for computer assignments. Travo is ...
The Canadian Traveller Problem on outerplanar graphs
summary: We focus on the PSPACE-complete k-Canadian Traveller Problem, where a weighted graph with a source s and a target t are given. This problem also has a hidden input of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum ...
TBA
summary: TBA
Recent Advances in Distributed Coloring
summary: The study of distributed graph algorithms aims to understand the limitations inherent to local computations. In a seminal paper, Linial (1992, SIAM J. Computing) introduced the LOCAL model to formalize this question. In this model, the input graph is seen as a communication network where vertices are computers. They ...
An acylic orientation problem with parity constraints
summary: Let G = (V, E) be a connected graph and T be a subset of the vertices. An orientation of G is a choice of a direction for each edge of the graph, it is said to be acylic if does not contain any directed cycle. An orientation of G ...
Ranking aggregation: graph-based methods and use in bioinformatics
summary: The problem of ranking aggregation is the following: we have a set of elements and a set of rankings of these elements as input, and we want a single ranking as output, which best reflects the set of rankings taken as input. The applications are manifold, especially in bioinformatics ...
Algèbres tridendriformes, arbres de Schröder et algèbre de Hopf
Les concepts d’algèbres dendriformes, respectivement tridendriformes décrivent l’action de certains éléments du groupe symétrique appelés les battages et respectivement les battages contractants sur l’ensemble des mots dont les lettres sont des éléments d’un alphabet, respectivement d'un monoïde. Un lien entre les algèbres dendriformes et tridendriformes ...
Page 1 / 24 »