A simple linear-time recognition algorithm for weakly quasi-threshold graphs

DOI10.1007/s00373-010-0983-0zbMath1235.05142OpenAlexW2058480081MaRDI QIDQ659727

Charis Papadopoulos, Stavros D. Nikolopoulos

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-010-0983-0

zbMATH Keywords

RecognitionCographsForbidden induced subgraphsLinear-time algorithmsWeakly quasi-threshold graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On characterizations for subclasses of directed co-graphs

Cites Work

• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Laplacian spectrum of weakly quasi-threshold graphs
• Complement reducible graphs
• A simple linear time algorithm for cograph recognition
• Algorithmic graph theory and perfect graphs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey

This page was built for publication: A simple linear-time recognition algorithm for weakly quasi-threshold graphs