36 citations · 96 across the 8 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2016
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is n…
cs.CC2016
A Note on the Complexity of Computing the Number of Reachable Vertices in a Digraph
Michele Borassi
In this work, we consider the following problem: given a digraph , for each vertex , we want to compute the number of vertices reachable from . In other words, we wa…
cs.CC2014★ 24 cited
Into the Square - On the Complexity of Quadratic-Time Solvable Problems
Michele Borassi, Pierluigi Crescenzi, Michel Habib
This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $…