Geodesic
Factoring directed graphs with respect to the cardinal product in polynomial time
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 593-601

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

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

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

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

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