An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs. (English) Zbl 1251.05173
Summary: In this paper, we consider the recognition problem on a class of perfectly orderable graphs, namely, the HHD-free graphs; such graphs do not contain any induced subgraph isomorphic to a house, a hole, or a domino. We prove properties of the HHD-free graphs which enable us to present an \(O(n m)\)-time and \(O(n+m)\)-space algorithm for determining whether a graph on n vertices and m edges is HHD-free; currently, this is the fastest algorithm for this problem. We also describe how the algorithm can be augmented to provide a certificate (an induced house, hole, or domino) whenever it decides that the input graph is not HHD-free, thus answering an open question posed by C. T. Hoàng and R. Sritharan [Theor. Comput. Sci. 259, No.1-2, 233-244 (2001)]. The certificate computation requires \(O(n+m)\) additional time and \(O(n)\) space.
Keywords:
HHD-free graphs; perfectly orderable graphs; certifying algorithms; recognition; house-, hole- or domino-free; HDD freeReferences:
| [1] | C. Berge, Färbung von Graphen deren sämtliche bzw deren ungerade Kreisse starr sind, Wiss. Z. Martin-Luther-Univ. Hale-Wittenberg Mathe.-Natur.; C. Berge, Färbung von Graphen deren sämtliche bzw deren ungerade Kreisse starr sind, Wiss. Z. Martin-Luther-Univ. Hale-Wittenberg Mathe.-Natur. |
| [2] | A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: A survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph classes: A survey, SIAM Monographs on Discrete Mathematics and Applications, 1999. · Zbl 0919.05001 |
| [3] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. of Math., 164, 51-229 (2006) · Zbl 1112.05042 |
| [4] | Chvátal, V., Perfectly ordered graphs, Ann. of Discrete Math., 21, 63-65 (1984) · Zbl 0559.05055 |
| [5] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press, Inc. · Zbl 1047.68161 |
| [6] | Eschen, E. M.; Johnson, J. L.; Spinrad, J. P.; Sritharan, R., Recognition of some perfectly orderable graph classes, Discrete Appl. Math., 128, 355-373 (2003) · Zbl 1019.68075 |
| [7] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press, Inc · Zbl 0541.05054 |
| [8] | Hayward, R., Meyniel weakly triangulated graphs I: co-perfect orderability, Discrete Appl. Math., 73, 199-210 (1997) · Zbl 0878.05035 |
| [9] | Hell, P.; Huang, J., Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs, SIAM J. Discrete Math., 18, 554-570 (2004) · Zbl 1069.05056 |
| [10] | Hoàng, C. T., On the complexity of recognizing a class of perfectly orderable graphs, Discrete Appl. Math., 66, 219-226 (1996) · Zbl 0854.68044 |
| [11] | Hoàng, C. T.; Khouzam, N., On brittle graphs, J. Graph Theory, 12, 391-404 (1988) · Zbl 0653.05059 |
| [12] | Hoàng, C. T.; Sritharan, R., Finding houses and holes in graphs, Theoret. Comput. Sci., 259, 233-244 (2001) · Zbl 0973.68184 |
| [13] | Kratsch, D.; McConnell, R. M.; Mehlhorn, K.; Spinrad, J., Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM J. Comput., 36, 326-353 (2006) · Zbl 1113.68112 |
| [14] | R.M. McConnell, J. Spinrad, Linear-time modular decomposition and efficient transitive orientation, in: Proc. 5th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA’94, 1994, 536-545.; R.M. McConnell, J. Spinrad, Linear-time modular decomposition and efficient transitive orientation, in: Proc. 5th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA’94, 1994, 536-545. · Zbl 0867.05068 |
| [15] | Middendorf, M.; Pfeiffer, F., On the complexity of recognizing perfectly orderable graphs, Discrete Math., 80, 327-333 (1990) · Zbl 0706.68058 |
| [16] | Nikolopoulos, S. D.; Palios, L., Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation, Algorithmica, 39, 95-126 (2004) · Zbl 1064.68073 |
| [17] | Nikolopoulos, S. D.; Palios, L., Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs, Discrete Math. and Theoret. Comput. Sci., 8, 65-82 (2006) · Zbl 1153.05331 |
| [18] | S.D. Nikolopoulos, L. Palios, An \(O ( n m )\); S.D. Nikolopoulos, L. Palios, An \(O ( n m )\) · Zbl 1214.05164 |
| [19] | Olariu, S., Weak bipolarizable graphs, Discrete Math., 74, 159-171 (1989) · Zbl 0666.05062 |
| [20] | Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019 |
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.
