Strong Products of Hypergraphs: Unique Prime Factorization Theorems and Algorithms
Strong Products of Hypergraphs: Unique Prime Factorization Theorems and Algorithms
复制标题
DOI：
10.1016/j.dam.2014.02.017
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
Marc Hellmuth;Manuel Noll;Lydia Ostermeier
中科院分区：
文献类型：
--
作者：
Marc Hellmuth;Manuel Noll;Lydia Ostermeier
众所周知，所有有限连通图都具有唯一的关于强图积的素因子分解（PFD），并且可以在多项式时间内计算。PFD计算的关键是构造所研究的图的所谓笛卡尔骨架。在这篇文章中，我们证明了每一个连通的瘦超图H有一个唯一的素因子分解关于正常和强（超图）的产品。当H是一个图时，这两个积都与通常的强图积一致。我们引入了超图的笛卡尔骨架的概念，作为图的笛卡尔骨架的自然推广，并证明了它是唯一定义的薄超图。此外，我们还证明了超图的笛卡尔骨架可以在O（|E| 2）时间，PFD可以在O（|V| 2| E|）时间，对于度和秩都有界的超图H=（V，E）.
It is well-known that all finite connected graphs have a unique prime factor decomposition (PFD) with respect to the strong graph product which can be computed in polynomial time. Essential for the PFD computation is the construction of the so-called Cartesian skeleton of the graphs under investigation. In this contribution, we show that every connected thin hypergraph H has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong graph product whenever H is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of hypergraphs can be determined in O (| E| 2) time and that the PFD can be computed in O (| V| 2| E|) time, for hypergraphs H=(V, E) with bounded degree and bounded rank.