Fast Symmetry Detection on Graphs

Markus Anders

Thu 2 November 2023 600.0 11:00am
Contact: Liang Zheng

Location: Innovation Space, Birch Building

Talks

Markus Anders
Markus Anders

Abstract

Exploitation of symmetry has a dramatic impact on the efficiency of algorithms in various fields. Before symmetries of a structure can be exploited, one first has to have algorithmic means to find the symmetries. Typically, this is achieved through modeling said structure as a graph, followed by an application of a practical graph isomorphism solver such as nauty, saucy, bliss, Traces, or dejavu.

In this talk, I will give a brief overview of recent progress on practical graph isomorphism solvers. This includes new randomized search strategies, a collection of implementation techniques, as well as theoretical lower bounds gauging design limitations.

Biography

Markus Anders is a PhD student in the Mathematics department of TU Darmstadt, Germany. His main research interests revolve around the algorithmic detection and exploitation of combinatorial symmetry, in particular in the context of Boolean satisfiability (SAT) solvers. Prior to this, Markus did his Master’s degree in Computer Science in Kaiserslautern.

You are on Aboriginal land.

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

arrow-left bars search times