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

DOI10.1007/S00373-010-0983-0zbMATH Open1235.05142OpenAlexW2058480081MaRDI QIDQ659727FDOQ659727

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

Recommendations

• Quasi-threshold graphs
• A simple linear time algorithm for cograph recognition
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Laplacian spectrum of weakly quasi-threshold graphs
• scientific article; zbMATH DE number 3896983

zbMATH Keywords

RecognitionCographsForbidden induced subgraphsLinear-time algorithmsWeakly quasi-threshold graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Linear-time recognition of double-threshold graphs
• On characterizations for subclasses of directed co-graphs
• A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
• Laplacian spectrum of weakly quasi-threshold graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659727)