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

DOI10.1007/S00373-010-0983-0MaRDI QIDQ659727zbMATHOpenAlexFDO

Authors Stavros D. Nikolopoulos, Charis Papadopoulos

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) Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)

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

Cites work

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

Cited in

(4)

• Laplacian spectrum of weakly quasi-threshold graphs
• A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
• On characterizations for subclasses of directed co-graphs
• Linear-time recognition of double-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)