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

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)

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

Cites work

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

Cited in

(6)

• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• Distinguishing threshold of graphs
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• Colinear Coloring on Graphs
• Recognition of Unigraphs through Superposition of Graphs (Extended Abstract)
• scientific article; zbMATH DE number 942492 (Why is no real title available?)

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)