The complexity of computing metric distances between partitions

DOI10.1016/0165-4896(81)90042-1zbMath0497.62049MaRDI QIDQ1170849

William H. E. Day

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

zbMATH Keywords

lattice; algorithm; clustering; complexity of computing metric distances; graph-theoretic representations; similarity of partitions

Mathematics Subject Classification ID

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, 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, 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