The Canadian Traveller Problem on outerplanar graphs

-- Pierre Bergé (LIMOS)

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 ...


-- Gervais Mendy Samuel Ouya (Université Cheikh Anta Diop de Dakar, LITA)

summary: TBA

Recent Advances in Distributed Coloring

-- Maxime Flin (Reykjavik University)

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

-- Matthieu Petiteau (Université Grenoble Alpes)

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

-- Adeline Pierrot (LISN, Galac)

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

-- Pierre Catoire (Univ. du Littoral)

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 ...

Canadian Traveller Problems in Temporal Graphs.

-- Minh Hang Nguyen (IRIF)

summary: We focus on the Canadian Traveller Problem, where a traveller aims to travel on a network from s to t with the minimum cost, considering that a maximum of k edges can be blocked. These edges remain hidden from the traveller until they visit one of their endpoints. We ...

Current trends in Optimal Stopping Problems and Machine Learning

-- Ini Adinya (LISN, Galac)

summary: Stochastic optimal stopping problems have a wide range of applications, from finance and economics to neuroscience, robotics, and energy management. Many real-world applications involve complex models that have driven the development of sophisticated numerical methods.
Recently, computational methods based on machine learning methods have been developed for solving such ...

Transversals in a collection of graphs with degree conditions

-- Luyi Li (LISN, Galac)

summary: Let G={G_1, G_2, ... , G_m} be a collection of n-vertex graphs on the same vertex set V (a graph system), and F be a simple graph with e(F) ≤ m. If there is an injection f: E(F) → [m] such that e &isinv E(G_{f(e)}) for each ...

Compact local certification of MSO properties for several tree-like parameters

-- Hugo Demaret (LISN, Galac)

summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...

Page 1 / 24 »