Displaying similar documents to “Factoring directed graphs with respect to the cardinal product in polynomial time II”

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

Wilfried Imrich, Werner Klöckl (2007)

Discussiones Mathematicae Graph Theory

Similarity:

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.

An attractive class of bipartite graphs

Rodica Boliac, Vadim Lozin (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.