This is about published papers
Here below the abstract of our new paper “Directing Road Networks by Listing Strong Orientations” presented at IWOCA2016. A connected road network with N nodes and L edges has K \leq L edges identified as one-way roads. In a feasible direction, these one-way roads are assigned a direction each, so that every node can reach[…]
Our paper “Listing Acyclic Orientations of Graphs with Single and Multiple Sources” has been accepted to be published at Latin American Theoretical Informatics Symposium, LATIN 2016 to be held in Ensenada, Mexico (April 11-15, 2016). The abstract follows. We study enumeration problems for the acyclic orientations of an undirected graph with n nodes and m[…]
Our paper “Clique Covering of Large Real-World Networks” has been accepted for publishing at 31st ACM Symposium on Applied Computing, that will be held in Pisa from 4th to 8th April 2016. Here the abstract is. The edge clique covering (ECC) problem deals with discovering a set of (possibly overlapping) cliques in a given network,[…]
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[…]
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[…]
It has been great year for the Italian Conference on Theoretical Computer Science. This 16th edition was in Florence and I was really happy to see several friends and nice people here. The conference has been hosted in a deconsecrated church owned by University of Florence. I passed many times in this street ignoring the presence[…]
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[…]