screen-shot-2010-08-12-at-12-11-31-pm1

On the several proofs about P and NP

Recently, I’ve found this nice web site that collects wrong proofs about P and NP relationship. https://www.win.tue.nl/~gwoegi/P-versus-NP.htm Currently there are 107 proofs. Probably, all of them are wrong (otherwise, probably we would know the guy) and the nice scoring function provided by Scott Aaranson here can be applied. This scoring function is the number of signs exhibited[…]

ALENEX16

ALENEX2016

Our paper “Computing Top-k Closeness Centrality Faster in Unweighted Graphs” has been accepted for ALENEX 2016 (Algorithms Engineering and Experiments). Thanks to all the coauthors Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi and Henning Meyerhenke. This work is the result of a merge between our work (see here) and the work by Elisabetta and Henning. It’s a pleasure to start this new collaboration. This is the abstract[…]

cropped-IMG_2409_2-Version-3-imp1

IWOCA2015

Our paper about “Enumerating Cyclic Orientations of a Graph” will be presented at IWOCA2015 in Verona! Thanks to all my coauthors: Alessio Conte, Roberto Grossi, Romeo Rizzi. The abstract follows. Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge[…]

Long-list

Enumeration Catalogue

Some months ago, a very nice web page came out. I am talking about the catalogue of enumeration algorithms by Kunihiro Wasa. There you can find an “Enumeration of Enumeration Algorithms and Its Complexity”. For each class of the followings: Geometry Graph Hypergraph Matroid Order Other Permutation SAT Set String several enumeration problems are enumerated. For[…]

KONICA MINOLTA DIGITAL CAMERA

ESA2015

Our paper “On Computing the Hyperbolicity of Real-World Graphs” has been accepted for ESA 2015 !!! Thanks to all my coauthors Michele Borassi, David Coudert, and Pierluigi Crescenzi. You can read the abstract here. The (Gromov) hyperbolicity is a topological property of a graph, which has been recently applied in several different contexts, such as the design of[…]

cl80N_H1

WWW2015

WWW2015 has been in Florence, at Fortezza da Basso. It’s a great event for the city and I’ve seen several friends around!