A Simple Linear-Time Recognition Algorithm for Weakly Quasi-Threshold Graphs |
| |
Authors: | Stavros D. Nikolopoulos Charis Papadopoulos |
| |
Affiliation: | 1. Department of Computer Science, University of Ioannina, P. O. Box 1186, 45110, Ioannina, Greece
|
| |
Abstract: | Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of {P 4, co-(2P 3)}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional ${{mathcal O}(n)}$ time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|