Factoring directed graphs with respect to the cardinal product in polynomial time

• Autorzy: Wilfried Imrich , Werner Klöckl
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

directed graphs; cardinal product; graph algorithms

Kategorie tematyczne

• 05C20: Directed graphs (digraphs), tournaments
• 05C75: Structural characterization of families of graphs
• 05C85: Graph algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 3
• Strony: 593-601

Daty

wydano

2007

otrzymano

2006-02-13

poprawiono

2006-10-17

zaakceptowano

2007-01-10

Twórcy

autor

Wilfried Imrich

• Chair of Applied Mathematics, Montanuniversität, 8700 Leoben, Austria

autor

Werner Klöckl

• Chair of Applied Mathematics, Montanuniversität, 8700 Leoben, Austria

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1385