Quasi-threshold graphs
| dc.citation.epage | 255 | en_US |
| dc.citation.issue | 3 | en_US |
| dc.citation.spage | 247 | en_US |
| dc.citation.volume | 69 | en_US |
| dc.citation.woscount | 17 | |
| dc.contributor.author | Yan, JH | en_US |
| dc.contributor.author | Chen, JJ | en_US |
| dc.contributor.author | Chang, GJ | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:02:25Z | |
| dc.date.available | 2014-12-08T15:02:25Z | |
| dc.date.issued | 1996-08-27 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.issn | 0166-218X | en_US |
| dc.identifier.journal | DISCRETE APPLIED MATHEMATICS | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/1095 | |
| dc.identifier.wosnumber | WOS:A1996VD36900004 | |
| dc.language.iso | en_US | en_US |
| dc.title | Quasi-threshold graphs | en_US |
| dc.type | Article | en_US |