Efficient parallel recognition algorithms of cographs and distance hereditary graphs

DOI10.1016/0166-218X(93)E0138-OzbMath0822.68079WikidataQ127908672 ScholiaQ127908672MaRDI QIDQ1345961

Elias Dahlhaus

Publication date: 9 October 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

cographshereditary graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items (17)

Recognizing cographs and threshold graphs through a classification of their edges ⋮ A faster parallel connectivity algorithm on cographs ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ On parallel recognition of cographs ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ Some new classes of open distance-pattern uniform graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ The Hamiltonian problem on distance-hereditary graphs ⋮ A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs ⋮ Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs ⋮ On the Letac-Massam conjecture and existence of high dimensional Bayes estimators for graphical models ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ Efficient parallel recognition of cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial characterization of read-once formulae
• Completely separable graphs
• Distance-hereditary graphs
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• An efficient parallel algorithm for planarity
• Complement reducible graphs
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• On a property of the class of n-colorable graphs
• Parallel algorithms for cographs and parity graphs with applications
• A Linear Recognition Algorithm for Cographs
• An Efficient Parallel Biconnectivity Algorithm
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• An O(logn) parallel connectivity algorithm
• Decomposition of Directed Graphs
• Learning read-once formulas with queries
• Dacey Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Operational Statistics. I. Basic Concepts
• Parallel algorithm for cograph recognition with applications
• Parallelism in random access machines

This page was built for publication: Efficient parallel recognition algorithms of cographs and distance hereditary graphs