Séminaire d'équipe GALaC

Le séminaire d'équipe de GALaC est organisé régulièrement le vendredi à 14h00 dans le bâtiment PCRI (650) au LISN.

Séminaires récents et à venir

Packing many dominating sets in a graph

-- Hossein Zaredehabadi (LISN)

summary: Given a graph G, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S. While classical studies focus on finding the smallest dominating set of G, our focus shifts to finding the ...

Decision-Theoretic Approaches in Learning-Augmented Algorithms

-- Georgii Melidi (LIP6)

summary: We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, as well as stochastic measures that ...


Faster diameter computation in graphs of bounded Euler genus

-- Giannos Stamoulis (CNRS, IRIF)

Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs ...

Les méandres arcs-en-ciel sur des chemins de Dyck

-- Benjamin Dequêne (Université de Leeds)

Un méandre (de longueur n) est une paire de correspondences non-croisées sur {1,...,n}. On peut le représenter sur le plan réel comme un paire d'ensemble de demi-cercles, qui ne s'intersentent pas deux à deux, reliant n points sur une droite. Cette représentation géométrique permet d'introduire différentes ...

Lattice structures of Gog and Magog triangles

-- Ludovic Schwob (LIGM, Combi)

summary: Gog and Magog triangles are simple combinatorial objects which are equienumerated. Howewer, the problem of finding an explicit bijection between these has been an open problem since the 80’s. These are related to other interesting objects such as alternating sign matrices, plane partitions or aztec diamond tillings.
All ...

See all

Translations: en