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

Dahlhaus, Elias (2000) Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition.
Published in: Journal of Algorithms Vol. 36 (2). pp. 205-240.

Abstract

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solve some algorithmic problems in graphs. This includes split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of Cicerone and di Stephano that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.


Actions:
Full text not available from this repository. (Request a copy)
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Aug 2011 08:42
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/324