×

A fully dynamic algorithm for modular decomposition and recognition of cographs. (English) Zbl 1062.68092

Summary: The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The input to the problem consists of a series of modifications to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold. In this paper, we solve the dynamic recognition problem for the class of cographs and some of its subclasses. Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition. We give the first fully dynamic algorithm for maintaining the modular decomposition tree of a cograph. We thereby obtain fully dynamic algorithms for the recognition of cographs, threshold graphs, and trivially perfect graphs. All these algorithms work in constant time per edge modification and \(O(d)\) time per \(d\)-degree vertex modification.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes—a Survey, SIAM Monographs in Discrete Mathematics and Applications, SIAM, Philadelphia, 1999.; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes—a Survey, SIAM Monographs in Discrete Mathematics and Applications, SIAM, Philadelphia, 1999.
[2] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 163-174 (1981) · Zbl 0463.05057
[3] Corneil, D.; Perl, Y.; Stewart, L., A linear recognition algorithm for cographs, SIAM J. Comput., 14, 4, 926-934 (1985) · Zbl 0575.68065
[4] A. Cournier, M. Habib, A new linear algorithm for modular decomposition, in: 19th International Colloquium (CAAP’94), 1994, lNCS 787, pp. 68-82.; A. Cournier, M. Habib, A new linear algorithm for modular decomposition, in: 19th International Colloquium (CAAP’94), 1994, lNCS 787, pp. 68-82. · Zbl 0938.05502
[5] E. Dahlhaus, J. Gustedt, R. McConnell, Efficient and practical modular decomposition, in: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97), New Orleans, LA, 1997, pp. 26-35.; E. Dahlhaus, J. Gustedt, R. McConnell, Efficient and practical modular decomposition, in: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’97), New Orleans, LA, 1997, pp. 26-35. · Zbl 1321.05255
[6] Deng, X.; Hell, P.; Huang, J., Linear time representation algorithms for proper circular arc graphs and proper interval graphs, SIAM J. Comput., 25, 2, 390-403 (1996) · Zbl 0858.05094
[7] Golumbic, M. C., Trivially perfect graphs, Discrete Math., 24, 105-107 (1978) · Zbl 0384.05057
[8] Hammer, P. L.; Simeone, B., The splittance of a graph, Combinatorica, 1, 275-284 (1981) · Zbl 0492.05043
[9] Hell, P.; Shamir, R.; Sharan, R., A fully dynamic algorithm for recognizing and representing proper interval graphs, SIAM J. Comput., 31, 1, 289-305 (2002) · Zbl 0992.68065
[10] Hsu, W.-L., On-line recognition of interval graphs in \(O(m+n logn)\) time, Lecture Notes Comput. Sci., 1120, 27-38 (1996)
[11] L. Ibarra, Fully dynamic algorithms for chordal graphs, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’99), Baltimore, MD, 1999, pp. 923-924.; L. Ibarra, Fully dynamic algorithms for chordal graphs, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’99), Baltimore, MD, 1999, pp. 923-924. · Zbl 0929.68087
[12] L. Ibarra, A fully dynamic algorithm for recognizing interval graphs using the clique-separator graph, Technical Report, University of Victoria, Vic., Canada, 2001.; L. Ibarra, A fully dynamic algorithm for recognizing interval graphs using the clique-separator graph, Technical Report, University of Victoria, Vic., Canada, 2001.
[13] Mahadev, N.; Peled, U., Threshold graphs and related topics. Threshold graphs and related topics, Annals of Discrete Mathematics, Vol. 56 (1995), Elsevier: Elsevier North-Holland, Amsterdam · Zbl 0852.05001
[14] R.M. McConnell, J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’94), ACM Press, New York, 1994, pp. 536-545.; R.M. McConnell, J.P. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’94), ACM Press, New York, 1994, pp. 536-545. · Zbl 0867.05068
[15] Muller, J.; Spinrad, J., Incremental modular decomposition, J. ACM, 36, 1, 1-19 (1989) · Zbl 0671.68030
[16] J. Spinrad, Two dimensional partial orders, Ph.D. Thesis, Department of Computer Science, Princeton University, Princeton, NJ, 1982.; J. Spinrad, Two dimensional partial orders, Ph.D. Thesis, Department of Computer Science, Princeton University, Princeton, NJ, 1982.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.