PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 27 | 3 | 593-601
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
27
Numer
3
Strony
593-601
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-02-13
poprawiono
2006-10-17
zaakceptowano
2007-01-10
Twórcy
  • Chair of Applied Mathematics, Montanuniversität, 8700 Leoben, Austria
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1385
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.