Efficient parallel modular decomposition (extended abstract)

DOI10.1007/3-540-60618-1_83MaRDI QIDQ6122232zbMATH OpenOpenAlexFDO

Authors Elias Dahlhaus

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60618-1_83

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Parallel comparability graph recognition and modular decomposition
• Efficient and practical algorithms for sequential modular decomposition
• scientific article; zbMATH DE number 1003286
• A survey of the algorithmic aspects of modular decomposition
• Incremental modular decomposition

Cites work

• \(P_ 4\)-trees and substitution decomposition
• An Efficient Parallel Biconnectivity Algorithm
• An O(logn) parallel connectivity algorithm
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Complement reducible graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• Efficient parallel recognition algorithms of cographs and distance hereditary graphs
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Incremental modular decomposition
• On Comparability and Permutation Graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Parallel Algorithm for Cograph Recognition with Applications

Cited in

(2)

• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Homogeneous sets and domination problems

This page was built for publication: Efficient parallel modular decomposition (extended abstract)

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