The strong direct product is one of the standard graph products. In 1992, Feigenbaum and Schäffer presented a polynomial-time algorithm to find the unique prime factorization of connected graphs under the strong direct product. In this paper, we show that weakly connected directed graphs have unique prime factorizations with respect to the strong direct product, and we give a polynomial-time algorithm to find the prime factorizations of such digraphs. This is an extension of Feigenbaum and Schäffer's work on factoring undirected graphs under the strong direct product and Imrich's work on factoring undirected graphs with respect to the weak direct product. We also investigate the problem of determining whether an algebra has the congruence extension property. We prove that this problem is complete for polynomial time.
展开▼
