Recognizing cographs and threshold graphs through a classification of their edges

DOI10.1016/S0020-0190(00)00041-7zbMath1339.05400MaRDI QIDQ294753

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

complexityparallel algorithmrecognitioncographsgraph partitionedge classificationthreshold graphs

Mathematics Subject Classification ID

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

Related Items

Colinear Coloring on Graphs, Recognition of Unigraphs through Superposition of Graphs (Extended Abstract), NP-completeness results for some problems on subclasses of bipartite and chordal graphs

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Complement reducible graphs
• 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
• The Comparability Graph of a Tree
• Parallel algorithm for cograph recognition with applications