Recognizing cographs and threshold graphs through a classification of their edges

DOI10.1016/S0020-0190(00)00041-7zbMATH Open1339.05400MaRDI QIDQ294753FDOQ294753

Authors: Stavros D. Nikolopoulos 

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000417?np=y

Recommendations

• scientific article; zbMATH DE number 1263242
• Representing graphs as the intersection of cographs and threshold graphs
• scientific article; zbMATH DE number 3896983
• Distinguishing threshold of graphs
• Boundary classes of graphs for some recognition problems
• Characterization and linear-time recognition of paired threshold graphs
• Enumerating threshold graphs and some related graph classes
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Recognizing weakly triangulated graphs by edge separability
• scientific article; zbMATH DE number 1617254

zbMATH Keywords

graph partitionparallel algorithmcomplexityrecognitioncographsedge classificationthreshold graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• Complement reducible graphs
• Matrix multiplication via arithmetic progressions
• The Comparability Graph of a Tree
• Parallel concepts in graph theory
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• Constant-time parallel recognition of split graphs
• Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
• PARALLEL RECOGNITION ALGORITHMS FOR GRAPHS WITH RESTRICTED NEIGHBOURHOODS
• Parallel algorithms for cographs and parity graphs with applications
• A Linear Recognition Algorithm for Cographs
• Parallel algorithm for cograph recognition with applications

Cited In (6)

• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Title not available (Why is that?)
• Distinguishing threshold of graphs
• Title not available (Why is that?)
• Recognition of Unigraphs through Superposition of Graphs (Extended Abstract)
• Colinear Coloring on Graphs

This page was built for publication: Recognizing cographs and threshold graphs through a classification of their edges

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