Factoring directed graphs with respect to the cardinal product in polynomial time II
Wilfried Imrich; Werner Klöckl
Discussiones Mathematicae Graph Theory (2010)
- Volume: 30, Issue: 3, page 461-474
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topWilfried Imrich, and Werner Klöckl. "Factoring directed graphs with respect to the cardinal product in polynomial time II." Discussiones Mathematicae Graph Theory 30.3 (2010): 461-474. <http://eudml.org/doc/270929>.
@article{WilfriedImrich2010,
abstract = {
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.
},
author = {Wilfried Imrich, Werner Klöckl},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {directed graphs; cardinal product; graph algorithms},
language = {eng},
number = {3},
pages = {461-474},
title = {Factoring directed graphs with respect to the cardinal product in polynomial time II},
url = {http://eudml.org/doc/270929},
volume = {30},
year = {2010},
}
TY - JOUR
AU - Wilfried Imrich
AU - Werner Klöckl
TI - Factoring directed graphs with respect to the cardinal product in polynomial time II
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 461
EP - 474
AB -
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.
LA - eng
KW - directed graphs; cardinal product; graph algorithms
UR - http://eudml.org/doc/270929
ER -
References
top- [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. Zbl0786.68076
- [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. Zbl1210.05125
- [3] W. Imrich, Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998) 119-144, doi: 10.1016/S0012-365X(98)00069-7. Zbl0955.68089
- [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. Zbl1142.05039
- [6] W. Klöckl, On the cardinal product, Ph.D. thesis (Montanuniversität Leoben, Austria, 2007). Zbl1142.05039
- [7] R. McKenzie, Cardinal multiplication of structures with a reflexive relation, Fund. Math. 70 (1971) 59-101. Zbl0228.08002
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.