標題: | Quasi-threshold graphs |
作者: | Yan, JH Chen, JJ Chang, GJ 應用數學系 Department of Applied Mathematics |
公開日期: | 27-八月-1996 |
摘要: | Quasi-threshold graphs are defined recursively by the following rules: (1) K-1 is a quasi-threshold graph, (2) adding a new vertex adjacent to all vertices of a quasi-threshold graph results in a quasi-threshold graph, (3) the disjoint union of two quasi-threshold graphs is a quasi-threshold graph. This paper gives some new equivalent definitions of a quasi-threshold graph. From them, linear time recognition algorithms follow. We also give linear time algorithms for the edge domination problem and the bandwidth problem in this class of graphs. |
URI: | http://hdl.handle.net/11536/1095 |
ISSN: | 0166-218X |
期刊: | DISCRETE APPLIED MATHEMATICS |
Volume: | 69 |
Issue: | 3 |
起始頁: | 247 |
結束頁: | 255 |
顯示於類別: | 期刊論文 |