All reports by Author Mauro Leoncini:

__
TR06-012
| 17th January 2006
__

Bruno Codenotti, Mauro Leoncini, Giovanni Resta#### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

__
TR03-081
| 10th October 2003
__

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini#### Computation of the Lov\'asz Theta Function for Circulant Graphs

Bruno Codenotti, Mauro Leoncini, Giovanni Resta

It is known that finding a Nash equilibrium for win-lose bimatrix

games, i.e., two-player games where the players' payoffs are zero

and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash

equilibrium for win-lose bimatrix games where the number of winning

positions ...
more >>>

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>