Geodesic
Factoring directed graphs with respect to the cardinal product in polynomial time II
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 461-474.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: directed graphs, cardinal product, graph algorithms 
@article{DMGT_2010_30_3_a8,
     author = {Imrich, Wilfried and Kl\"ockl, Werner},
     title = {Factoring directed graphs with respect to the cardinal product in polynomial time {II}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {461--474},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a8/}
}
TY  - JOUR
AU  - Imrich, Wilfried
AU  - Klöckl, Werner
TI  - Factoring directed graphs with respect to the cardinal product in polynomial time II
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 461
EP  - 474
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a8/
LA  - en
ID  - DMGT_2010_30_3_a8
ER  - 
%0 Journal Article
%A Imrich, Wilfried
%A Klöckl, Werner
%T Factoring directed graphs with respect to the cardinal product in polynomial time II
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 461-474
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a8/
%G en
%F DMGT_2010_30_3_a8
Imrich, Wilfried; Klöckl, Werner. Factoring directed graphs with respect to the cardinal product in polynomial time II. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 461-474. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a8/

[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.

[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.

[3] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7.

[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.

[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.

[6] W. Klöckl, On the cardinal product, Ph.D. thesis (Montanuniversität Leoben, Austria, 2007).

[7] R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971) 59-101.