By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1507,
author = {Wilfried Imrich and Werner Kl\"ockl},
title = {Factoring directed graphs with respect to the cardinal product in polynomial time II},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {461-474},
zbl = {1217.05100},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1507}
}
Wilfried Imrich; Werner Klöckl. Factoring directed graphs with respect to the cardinal product in polynomial time II. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 461-474. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1507/
[000] [1] 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. | Zbl 0786.68076
[001] [2] M. Hellmuth, W. Imrich, W. Klöckl and P. Stadler, Approximate graph products, Europ. J. Combinatorics 30 (2009) 1119-1133, doi: 10.1016/j.ejc.2008.09.006. | Zbl 1210.05125
[002] [3] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. | Zbl 0955.68089
[003] [4] 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.
[004] [5] W. Imrich and W. Klöckl, Factoring directed graphs with respect to the cardinal product in polynomial time, Discuss. Math. Graph Theory 27 (2007) 593-601, doi: 10.7151/dmgt.1385. | Zbl 1142.05039
[005] [6] W. Klöckl, On the cardinal product, Ph.D. thesis (Montanuniversität Leoben, Austria, 2007). | Zbl 1142.05039
[006] [7] R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971) 59-101. | Zbl 0228.08002