Computational complexity of digraph decomposition and the congruence extension property for algebras

Date
2002-01-01
Authors
Becker, Joy
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Abstract

The strong direct product is one of the standard graph products. In 1992, Feigenbaum and Schaffer 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 Schaffer'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.

Description
Keywords
Mathematics
Citation