Abstract
In this article we present the L2-section, a tool used to represent a hypergraph in terms of an “advanced graph” and results leading to first algorithm, in O(nm), for a bounded-rank, bounded-degree hypergraph H, which factorizes H in prime factors. The paper puts a premium on the characterization of the prime factors of a hypergraph, by exploiting isomorphisms between the layers in the 2-section, as returned by a standard graph factorization algorithm, such as the one designed by Imrich and Peterin.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berge, C.: Hypergraphs. North Holland, Amsterdam (1989)
Bretto, A.: Introduction to hypergraph theory and its use in engineering and image processing. Advances in imaging and electron physics 131 (2004)
Bretto, A.: Hypergraphs and the helly property. Ars Combinatoria 78, 23–32 (2006)
Imrich, W., Klavžar, S., Rall, D.F.: Topics in graph theory. Graphs and their Cartesian product. A K Peters, Wellesley (2008)
Imrich, W., Peterin, I.: Recognizing cartesian products in linear time. Discrete Mathematics 307, 472–483 (2007)
Imrich, W., Pisanski, T., Žerovnik, J.: Recognizing cartesian graph bundles. Discrete Mathematics 167-168, 393–403 (1997)
Peterin, I.: Game chromatic number of cartesian product graphs. Electronic Notes in Discrete Mathematics 29, 353–357 (2007)
Sabidussi, G.: Graph multiplication. Mathematische Zeitschrift 72 (1960)
Vesel, A.: Channel assignment with separation in the cartesian product of two cycles. In: Proceedings of the 24th International Conference on Information Technology Interfaces (2002)
Vizing, V.G.: The cartesian product of graphs. Vycisl. Sistemy 9, 30–43 (1963)
Zhang, Y., Sun, X.: The antimagicness of the cartesian product of graphs. Theor. Comput. Sci. 410(8-10), 727–735 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bretto, A., Silvestre, Y. (2010). Factorization of Cartesian Products of Hypergraphs. In: Thai, M.T., Sahni, S. (eds) Computing and Combinatorics. COCOON 2010. Lecture Notes in Computer Science, vol 6196. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14031-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-14031-0_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14030-3
Online ISBN: 978-3-642-14031-0
eBook Packages: Computer ScienceComputer Science (R0)