標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. A1996VD36900004.pdf