  Listing triangles is a fundamental graph problem with many applications, and
large graphs require fast algorithms. Vertex ordering allows the orientation of
edges from lower to higher vertex indices, and state-of-the-art triangle
listing algorithms use this to accelerate their execution and to bound their
time complexity. Yet, only basic orderings have been tested. In this paper, we
show that studying the precise cost of algorithms instead of their bounded
complexity leads to faster solutions. We introduce cost functions that link
ordering properties with the running time of a given algorithm. We prove that
their minimization is NP-hard and propose heuristics to obtain new orderings
with different trade-offs between cost reduction and ordering time. Using
datasets with up to two billion edges, we show that our heuristics accelerate
the listing of triangles by an average of 38% when the ordering is already
given as an input, and 16% when the ordering time is included.

Data Structures and Algorithms;Social and Information Networks