Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

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

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint