Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

DOI10.1006/JAGM.2000.1090zbMATH Open0961.68152OpenAlexW2103191280MaRDI QIDQ4500853FDOQ4500853

Authors: Elias Dahlhaus 

Publication date: 27 August 2000

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0286cc8442b7bb554bf8f8258544d53029a98703

Recommendations

• Parallel algorithms for parity graphs
• Constant-time parallel recognition of split graphs
• A fast parallel algorithm to recognize partitionable graphs
• Parallel algorithms for cographs and parity graphs with applications

zbMATH Keywords

parallel parity graph recognition algorithm

Mathematics Subject Classification ID

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

Cited In (30)

• Detecting 2-joins faster
• \(O(m\log n)\) split decomposition of strongly-connected graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• The bi-join decomposition
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Quick separation in chordal and split graphs
• \(O(m \log n)\) split decomposition of strongly connected graphs
• A note on computing set overlap classes
• Linear-time modular decomposition of directed graphs
• Word-representability of graphs with respect to split recomposition
• Solving some NP-complete problems using split decomposition
• Practical and efficient split decomposition via graph-labelled trees
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Practical and efficient circle graph recognition
• Algorithmic aspects of a general modular decomposition theory
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Consecutive ones property testing: cut or swap
• A polynomial kernel for distance-hereditary vertex deletion
• On polygon numbers of circle graphs and distance hereditary graphs
• Vertex-minors of graphs: a survey
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Circle graph isomorphism in almost linear time
• Some results on more flexible versions of Graph Motif
• Phylogenetic graph models beyond trees
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

This page was built for publication: Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

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