TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 28.09.2017



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

A General Framework for Triangle Listing

Mark Ortmann (University of Konstanz)

Listing all triangles in a graph is a fundamental problem in the anal-
ysis of networks. Hence, it comes as no surprise that a wide variety of
algorithms has been introduced which tackle this problem. In this talk
we show that all approaches from the literature have a common abstrac-
tion. Our unifying framework highlights that these seemingly different
algorithms are in fact instantiations of a single generic procedure, and
even suggests some additional variants. More importantly, it yields par-
simonious implementations that are in general more efficient than those
described in the original works and reveal where algorithmic improvements
are likely to be made.
In addition, in this talk, we show that the running time of nearly every
triangle listing variant is in \(O(a(G)m)\), where \(a(G)\) is the arboricity of the
graph and \(m\) the number of edges. So far this bound has only been proven
for Chiba and Nishizeki’s (SIAM J. Computing, 1985) triangle listing
algorithm. Finally, algorithmic experimentation reveals that an improved
implementation of exactly this algorithm outperforms all subsequently
proposed algorithms.


Mark Ortmann
TEL 512

Back to the research colloquium site.



Schnellnavigation zur Seite über Nummerneingabe