Discussiones Mathematicae Graph Theory 30(3) (2010)
461-474
doi: 10.7151/dmgt.1507
Wilfried Imrich and Werner Klöckl
Chair of Applied Mathematics
Montanuniversität, 8700 Leoben, Austria
e-mail: | wilfried.imrich@mu-leoben.at |
e-mail: | werner.kloeckl@mu-leoben.at |
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.
Keywords: directed graphs, cardinal product, graph algorithms.
2010 Mathematics Subject Classification: 05C20, 05C76, 05C85, 05C75.
[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. |
Received 16 July 2009
Revised 7 October 2009
Accepted 12 October 2009