Quasi-threshold graphs
type: Item
instance of: scholarly article
title: Quasi-threshold graphs
zbMATH Open document ID: 0857.05082
DOI: 10.1016/0166-218X(96)00094-7
author: Jing-Ho Yan
author: Jer-Jeong Chen
author: Gerard Jennhwa Chang
published in: Discrete Applied Mathematics
publication date: 1997-02-26T00:00:00Z
review text: 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. The paper gives some new equivalent definitions of quasi-threshold graph. From them, linear time recognition algorithms follow. The paper also presents linear time algorithms for the edge domination problem and the bandwidth problem in this class of graphs.
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 933099
zbMATH Keywords: quasi-threshold graph
zbMATH Keywords: recognition
zbMATH Keywords: domination
zbMATH Keywords: bandwidth
MaRDI profile type: Publication
cites work: Distance-hereditary graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Complement reducible graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Q3222876
cites work: Q3270978
cites work: Trivially perfect graphs
cites work: The complexity of comparability graph recognition and coloring
cites work: Q4281626
cites work: Q3203054
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: The Comparability Graph of a Tree
cites work: A Note on "The Comparability Graph of a Tree"
description: scientific article; zbMATH DE number 933099