Minimal separators in \(P_4\)-sparse graphs. (English) Zbl 1087.05055
Summary: We determine the minimal separators of \(P_{4}\)-sparse graphs and establish bounds on their number. Specifically, we show that a \(P_{4}\)-sparse graph \(G\) on \(n\) vertices and \(m\) edges has fewer than \(2n/3\) minimal separators of total description size at most \(4m/3\). The bound on the number of minimal separators is tight and is also tight for the class of cographs, a well-known subclass of the \(P_{4}\)-sparse graphs. Our results enable us to present a linear-time and linear-space algorithm for computing the number of minimal separators of a given \(P_{4}\)-sparse graph; the algorithm can be modified to report the minimal separators of the input graph in linear time and space as well.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C17 | Perfect graphs |
References:
| [1] | Berry, A., Graph extremities and minimal separation, (Proceedings of the Fourth International Conference JIM 2003: Knowledge Discovery and Discrete Mathematics. Proceedings of the Fourth International Conference JIM 2003: Knowledge Discovery and Discrete Mathematics, Metz, France (2003)) |
| [2] | Berry, A.; Bordat, J.-P., Triangulated and weakly triangulated graphssimpliciality in vertices and edges, (Proceedings of the Sixth International Conference on Graph Theory. Proceedings of the Sixth International Conference on Graph Theory, Luminy, France (2000)) |
| [3] | Berry, A.; Bordat, J.-P.; Cogis, O., Generating all the minimal separators of a graph, Internat. J. Foundations of Comput. Sci., 11, 397-404 (2000) · Zbl 1320.05120 |
| [4] | A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM 1999.; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM 1999. · Zbl 0919.05001 |
| [5] | A. Bretscher, D. Corneil, M. Habib, C. Paul, A simple linear time LexBFS cograph recognition algorithm, in: Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’03), Lecture Notes in Computer Science, vol. 2880, Springer, Berlin, 2003, pp. 119-130.; A. Bretscher, D. Corneil, M. Habib, C. Paul, A simple linear time LexBFS cograph recognition algorithm, in: Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’03), Lecture Notes in Computer Science, vol. 2880, Springer, Berlin, 2003, pp. 119-130. · Zbl 1255.68108 |
| [6] | Corneil, D. G.; Olariu, S.; Stewart, L., Asteroidal triple-free graphs, SIAM J. Discrete Math., 10, 399-430 (1997) · Zbl 0884.05075 |
| [7] | Corneil, D. G.; Perl, Y.; Stewart, L. K., A linear recognition algorithm for cographs, SIAM J. Comput., 14, 926-934 (1985) · Zbl 0575.68065 |
| [8] | A. Cournier, M. Habib, A new linear algorithm for modular decomposition, in: Proceedings of the 19th International Colloquium on Trees in Algebra and Programming (CAAP’94), Lecture Notes in Computer Science, vol. 787, Springer, Berlin, 1994, pp. 68-84.; A. Cournier, M. Habib, A new linear algorithm for modular decomposition, in: Proceedings of the 19th International Colloquium on Trees in Algebra and Programming (CAAP’94), Lecture Notes in Computer Science, vol. 787, Springer, Berlin, 1994, pp. 68-84. · Zbl 0938.05502 |
| [9] | Dahlhaus, E.; Gustedt, J.; McConnell, R. M., Efficient and practical algorithms for sequential modular decomposition, J. Algorithms, 41, 360-387 (2001) · Zbl 1017.68154 |
| [10] | E. Dahlhaus, P. Hammer, F. Maffray, S. Olariu, On domination elimination orderings and domination graphs, in: Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’94), Lecture Notes in Computer Science, vol. 903, Springer, Berlin, 1994, pp. 81-92.; E. Dahlhaus, P. Hammer, F. Maffray, S. Olariu, On domination elimination orderings and domination graphs, in: Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’94), Lecture Notes in Computer Science, vol. 903, Springer, Berlin, 1994, pp. 81-92. · Zbl 1530.05142 |
| [11] | Fulkerson, D. R.; Gross, O. A., Incident matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 |
| [12] | M. Habib, F. de Montgolfier, C. Paul, A simple linear-time modular decomposition algorithm for graphs, using order extension, in: Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT’04), Lecture Notes in Computer Science, vol. 3111, Springer, Berlin, 2004, pp. 187-198.; M. Habib, F. de Montgolfier, C. Paul, A simple linear-time modular decomposition algorithm for graphs, using order extension, in: Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT’04), Lecture Notes in Computer Science, vol. 3111, Springer, Berlin, 2004, pp. 187-198. · Zbl 1095.68622 |
| [13] | C. Hoàng, Perfect graphs, Ph.D. Thesis, McGill University, Montreal, Canada, 1985.; C. Hoàng, Perfect graphs, Ph.D. Thesis, McGill University, Montreal, Canada, 1985. |
| [14] | Giakoumakis, V.; Vanherpe, J., On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs, Theoret. Comput. Sci., 180, 269-286 (1997) · Zbl 0893.05017 |
| [15] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press, Inc.: Academic Press, Inc. New York · Zbl 0541.05054 |
| [16] | Golumbic, M. C.; Goss, C. F., Perfect elimination and chordal bipartite graphs, J. Graph Theory, 2, 155-163 (1978) · Zbl 0411.05060 |
| [17] | Jamison, B.; Olariu, S., \(P_4\)-reducible graphs a class of uniquely tree representable graphs, Stud. Appl. Math., 81, 79-87 (1989) · Zbl 0699.05054 |
| [18] | Jamison, B.; Olariu, S., Recognizing \(P_4\)-sparse graphs in linear time, SIAM J. Comput., 21, 381-406 (1992) · Zbl 0763.05093 |
| [19] | Jamison, B.; Olariu, S., A tree representation for \(P_4\)-sparse graphs, Discrete Appl. Math., 35, 115-129 (1992) · Zbl 0763.05092 |
| [20] | Jamison, B.; Olariu, S., Linear-time optimization algorithms for \(P_4\)-sparse graphs, Discrete Appl. Math., 61, 155-175 (1995) · Zbl 0831.68075 |
| [21] | H. Lerchs, On cliques and kernels, Technical Report, Department of Computer Science, University of Toronto, March 1971.; H. Lerchs, On cliques and kernels, Technical Report, Department of Computer Science, University of Toronto, March 1971. |
| [22] | McConnell, R. M.; Spinrad, J., Linear-time modular decomposition and efficient transitive orientation of comparability graphs, (Proceedings of the Fifth ACM-SIAM Symposium on Discrete Algorithms (SODA’94) (1994)), 536-545 · Zbl 0867.05068 |
| [23] | Roberts, F. S., Indifference graphs, (Harary, F., Proof Techniques in Graph Theory (1969), Academic Press), 139-146 · Zbl 0193.24205 |
| [24] | Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602 |
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.
