A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements |
| |
Authors: | Frank Pok Man Chu |
| |
Affiliation: | aDepartment of Computer Science, University of Toronto, 10 King's College Road, Toronto, ON, M5S 3G4, Canada |
| |
Abstract: | We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P4 or a C4 when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19]. |
| |
Keywords: | Algorithms Combinatorial problems Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|