The complexity of computing metric distances between partitions
From MaRDI portal
Publication:1170849
DOI10.1016/0165-4896(81)90042-1zbMath0497.62049MaRDI QIDQ1170849
Publication date: 1981
Published in: Mathematical Social Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0165-4896(81)90042-1
lattice; algorithm; clustering; complexity of computing metric distances; graph-theoretic representations; similarity of partitions
62H30: Classification and discrimination; cluster analysis (statistical aspects)
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Certain calculational aspects of the clusterization problem, Clustering and isolation in the consensus problem for partitions, The role of complexity in comparing classifications, An efficient algorithm for computing the distance between close partitions, Properties of Levenshtein metrics on sequences, Two local dissimilarity measures for weighted graphs with application to protein interaction networks, Transfer distance between partitions and search of dense zones in graphs, SEP/COP: an efficient method to find the best partition in hierarchical clustering based on a new cluster validity index, Approximating minimum-length-sequence metrics: A cautionary note, A computationally efficient approximation to the nearest neighbor interchange metric, Comparison of classifications using measures intermediate between metric dissimilarity and consensus similarity, Consensus-based partitions in the space of ordered partitions, On the use of ordered sets in problems of comparison and consensus of classifications, Consensus of partitions: a constructive approach, Lattice-based similarity measures between ordered trees, Consensus system for solving conflicts in distributed systems, Comparison of algorithms in graph partitioning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Metrics on spaces of finite trees
- A metric and an ordering on sets
- Validity of clusters formed by graph-theoretic cluster methods
- On the computational power of pushdown automata
- Multidimensional scaling of measures of distance between partitions
- Theory of equivalence relations
- A Comparison And Evaluation Of Graph Theoretical Clustering Technioues
- On clustering with chernoff-type faces
- Approximating Symmetric Relations by Equivalence Relations
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs