TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 28.09.2017

isti-logo

Page Content

to Navigation

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.

 

Date
Speaker
Location
Language
28.09.2017
16:15
Mark Ortmann
TEL 512
English

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe