Cartesian product of hypergraphs: properties and algorithms

Alain Bretto
(University of Caen)
Yannick Silvestre
(University of Caen)
Thierry Vallée
(University of Caen)

Cartesian products of graphs have been studied extensively since the 1960s. They make it possible to decrease the algorithmic complexity of problems by using the factorization of the product. Hypergraphs were introduced as a generalization of graphs and the definition of Cartesian products extends naturally to them. In this paper, we give new properties and algorithms concerning coloring aspects of Cartesian products of hypergraphs. We also extend a classical prime factorization algorithm initially designed for graphs to connected conformal hypergraphs using 2-sections of hypergraphs.

In Evangelos Markakis and Ioannis Milis: Proceedings Fourth Athens Colloquium on Algorithms and Complexity (ACAC 2009), Athens, Greece, August 20-21, 2009, Electronic Proceedings in Theoretical Computer Science 4, pp. 22–28.
Published: 30th September 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.4.3 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org