ArticleOriginal scientific text
Title
Factoring directed graphs with respect to the cardinal product in polynomial time
Authors 1, 1
Affiliations
- Chair of Applied Mathematics, Montanuniversität, 8700 Leoben, Austria
Abstract
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
Keywords
directed graphs, cardinal product, graph algorithms
Bibliography
- J. Feigenbaum and A.A. Schäffer, Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math. 109 (1992) 77-102, doi: 10.1016/0012-365X(92)90280-S.
- W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7.
- W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, New York, 2000), Structure and recognition, With a foreword by Peter Winkler.
- R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971) 59-101.
Pages:
593-601
Main language of publication
English
Received
2006-02-13
Accepted
2006-10-17
Published
2007
DOI: 10.7151/dmgt.1385
Exact and natural sciences