Discussiones Mathematicae Graph Theory 30(3) (2010)
Wilfried Imrich and Werner Klöckl
Chair of Applied Mathematics
Montanuniversität, 8700 Leoben, Austria
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.
|||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.|
|||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.|
|||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.|
|||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.|
|||W. Klöckl, On the cardinal product, Ph.D. thesis (Montanuniversität Leoben, Austria, 2007).|
|||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