Abstract
We propose an O(n 4) algorithm to build the modular decomposition tree of hypergraphs of dimension 3 and show how this algorithm can be generalized to compute efficiently the decomposition of hypergraphs of fixed dimension k.
This work has been supported by MURST 40% Algoritmi e strutture di calcolo and ASMICS 2 Nℴ 6317.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alain Cournier and Michel Habib. A new linear algorithm for modular decomposition. In Sophie Tison, editor, Trees in algebra and programming, CAAP '94: 19th international colloquium, LNCS 787, pages 68–84, 1994.
A. Ehrenfeucht, H.N. Gabow, R.M. McConnell, and S.J. Sullivan. An O(n 2) divide and conquer algorithm for the prime tree decomposition of 2-structures. Journal of Algorithms, 16:283–294, 1994.
A. Ehrenfeucht and G. Rozenberg. Theory of 2-structures, part 2: representations through labeled tree families. Theoretical Computer Science, 70:305–342, 1990.
Andrzej Ehrenfeucht and Ross M. McConnell. A k-structure generalization of the theory of 2-structures. Theoretical Computer Science, 132:209–227, 1994.
A. Engelfriet, T. Harjan, A. Proskurowsky, and G. Rozenberg. Survey on graphs as 2-structures and parallel complexity of decomposition. Technical Report TR9306, University of Leiden, Department of Computer Science, 1993.
M.C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
Ross M. McConnell and Jeremy P. Spinrad. Linear-time modular decomposition of undirected graphs and efficient transitive orientation of comparability graphs. In 5th ACM-SIAM Symposium on Discrete Algorithms, pages 536–545, 1994.
R.H. Möhring. Algorithmic aspects of comparability graphs and interval graphs. In I. Rival, editor, Graphs and Orders, pages 41–101. D. Reidel, Boston, 1985.
R.H. Möhring. Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and boolean functions. Annals of Operations Research, 4:195–225, 1985/6.
R.H. Möhring and F.J. Radermacher. Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics, 19:257–356, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bonizzoni, P., Della Vedova, G. (1995). Modular decomposition of hypergraphs. In: Nagl, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 1995. Lecture Notes in Computer Science, vol 1017. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60618-1_84
Download citation
DOI: https://doi.org/10.1007/3-540-60618-1_84
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60618-5
Online ISBN: 978-3-540-48487-5
eBook Packages: Springer Book Archive