Tag: Plateau seminar

VERTEX DISTINGUISHING COLORINGS OF GRAPHS

-- Professor Mariusz Wozniak (Department of Discrete Mathematics, AGH University, Cracow, Poland)

Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to ...

The coloring problem in clique-hypergraphs of graphs

-- Pr. Liying Kang (Department of Mathematics, Shanghai University, China)

ABSTRACT: A maximal clique of a graph is a clique not properly contained in any other clique. A \(k\)-clique coloring of a graph is an assignment of a \(k\) colors to the vertices of \(G\) such that no maximal clique with at least two vertices is monochromatic. The clique-chromatic ...

Minimizing the number of unhappy singles

-- Chien-Chung Huang (Gothenburg)

Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties. A matching M is said to be stable if there is ...

Prophet inequalities and secretary problem: a new approach.

-- Nguyen Kim Thang (IBISC)

In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...

Complexité de comptage des opérateurs d'intégration

-- Hugo Férée (Université de Lille)

L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...

Universal computation and asymptotic behaviour in symbolic dynamics.

-- Benjamin Hellouin (Universidad Andrés Bello (Santiago))

Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...

Highly Resource-limited Distributed Systems

-- Matthias Függer (Max-Planck-Institut)

In this talk I would like to advocate the study of non-classical distributed systems whose computing nodes can perform only simple computations under highly restricted communication mechanisms and memory capabilities. I will present two problems, we are currently working on, one from chip design and one from biology, showing that ...

Amortized Averaging Algorithms for Approximate Consensus

-- Thomas Nowak (LRI)

We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This allows their decision time to drop from being exponential in ...

Lire un programme ou l'exécuter : quelle différence ?

-- Mathieu Hoyrup (LORIA)

Que peut-on savoir d'une fonction si elle nous est présentée : - sous forme d'un programme calculant cette fonction, - sous forme d'une boîte noire permettant de connaître les valeurs de cette fonction sur toutes les entrées. Disposer d'un programme donne au moins autant d'information qu'avoir accès ...

Game theory applied to Protection against SIS Epidemics in Networks

-- Eitan Altman (INRIA)

Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. In this work, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. We assume ...

Page 1 / 2 »