  The three standard products (the Cartesian, the direct and the strong
product) of undirected graphs have been wellinvestigated, unique prime factor
decomposition (PFD) are known and polynomial time algorithms have been
established for determining the prime factors.
  For directed graphs, unique PFD results with respect to the standard products
are known. However, there is still a lack of algorithms, that computes the PFD
of directed graphs with respect to the direct and the strong product in
general. In this contribution, we focus on the algorithmic aspects for
determining the PFD of directed graphs with respect to the strong product.
Essential for computing the prime factors is the construction of a so-called
Cartesian skeleton. This article introduces the notion of the Cartesian
skeleton of directed graphs as a generalization of the Cartesian skeleton of
undirected graphs. We provide new, fast and transparent algorithms for its
construction. Moreover, we present a first polynomial time algorithm for
determining the PFD with respect to the strong product of arbitrary connected
digraphs.
