Efficient maximal cliques enumeration in weakly closed graphs
summary: We show that the algorithm presented in [J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448-464, 2020] can be modified to have enumeration time complexity αO(n·poly(c)). Here parameter ...
Coordonnées explicites pour le s-permutoèdre
En 2019, Viviane Pons et Cesar Ceballos ont introduit une généralisation de l'ordre faible avec un paramètre s qui est un vecteur d'entiers. Ils ont conjecturé (et prouvé en dimensions 2 et 3) que cette structure admettait une réalisation géométrique comme complexe polytopal. En collaboration avec Daniel Tamayo ...
Auction mechanisms for allocation and pricing in Edge Computing
summary: Soon, billions of devices will be connected to the Internet, and most of them will need external resources to store and process their data. Edge Computing can benefit these devices by making these resources available at the network's edges to be closer to the user. However, these offered ...
A Closure Lemma for tough graphs and Hamiltonian degree conditions
summary: A graph G is Hamiltonian if there exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G−S is at most |S|/t. We extended the theorem of ...
Memory-Optimization for Self-Stabilizing Distributed Algorithms
summary: Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it ...
Algorithmes de partitionnement par comparaison de paires
On cherche à reconstruire une partition d'un ensemble donné en envoyant des paires d'éléments à un oracle qui nous indique s'ils appartiennent à la même partie de la partition. Nous cherchons les algorithmes qui retrouvent la partition en un minimum de questions à l'oracle. Ce problème ...
Algorithms for the Metric Dimension problem on directed graphs
summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem ...
Complexity of positional games
summary: Positional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game, with the rows, columns, and diagonals forming the hyperedges and the ...
Language-theoretic methods in semigroup theory
Language-theoretic methods in combinatorial group theory go back to the fundamental work by Anisimov in the 1970s. Since then, the area has exploded, including such deep theorems as the Muller-Schupp theorem: a group has context-free word problem if and only if it is virtually free. In this talk, I will ...
The Domino Snake Problem
summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this ...