Speaker
Marc Hellmuth
(Bioinformatics, Saarland University)
Description
The ``usual'' Cartesian skeleton, established by Hammack and Imrich,
is a substructure of graphs and provides the essential information
in order to decompose given undirected graphs w.r.t. the direct and
the strong product.
In this talk, we discuss two generalizations of the Cartesian skeleton for undirected hypergraphs and directed graphs. These generalizations enable us to show that every thin hypergraph has a unique prime factor decomposition (PFD) w.r.t. the strong product. Moreover, these results are used to design algorithms that determine the PFD w.r.t. the strong product of directed graphs and thin hypergraphs in polynomial time.
Primary author
Marc Hellmuth
(Bioinformatics, Saarland University)
