Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cardinal product

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

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

100%

Imrich W., Klöckl W.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 3

593-601

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.

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

100%

Imrich W., Klöckl W.

Discussiones Mathematicae Graph Theory

2010

tom 30

nr 3

461-474

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Imrich W.

2 Klöckl W.

1 2010

1 2007

Wyniki wyszukiwania

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

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