IPM Calendar 
Friday 29 March 2024   Today  
Events for day: Monday 22 January 2018    
           14:00 - 15:00     Lecture
Algorithms for Finding the Prime Factors of Product Graphs

School
MATHEMATICS

The talk discusses fast algorithms for the prime factorization of undirected graphs with respect to the Cartesian, the direct and the strong product. There is a linear algorithm for the factorization of connected graphs with respect to the Cartesian product, All other factorization algorithms with respect to a given product operation consist of reduction algorithms that lead to the factorization of so-called Cartesian skeletons with respect to the Cartesian product, and subsequent construction of the prime factors with respect to the given product operation. It is then explained how one can extend the method to the prime factorization of dire ...