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