Tag: Team seminar
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 ...
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 ...
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 ...
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 ...
The fixed-point construction in tilings
summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them. It defines the set of colorings of the infinite grid that respects these adjacency constraints. Such a coloring is called a tiling. Given a tileset as input, a question naturally arises: does ...
Lattice properties of acyclic pipe dreams
summary: Pipe dreams were introduced by Bergeron and Billey in order to study Schubert polynomials and encode the algebraic structure of the symmetric group. In particular, with well-chosen parameters, they have the combinatorial structure of the Tamari lattice, a well-known quotient of the weak order on permutations. In this presentation ...
Proper vertex coloring with odd occurrence - Probabilistic approach
summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints. A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors. For a graph G, the chromatic number χ(G) is ...