The complexity of computing metric distances between partitions

DOI10.1016/0165-4896(81)90042-1MaRDI QIDQ1170849zbMATH OpenOpenAlexFDO

Authors W. 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

algorithmclusteringcomplexity of computing metric distancesgraph-theoretic representationslatticesimilarity of partitions

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A Comparison And Evaluation Of Graph Theoretical Clustering Technioues
• A metric and an ordering on sets
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximating Symmetric Relations by Equivalence Relations
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3504320 (Why is no real title available?)
• scientific article; zbMATH DE number 3448387 (Why is no real title available?)
• scientific article; zbMATH DE number 3228308 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• scientific article; zbMATH DE number 3231693 (Why is no real title available?)
• Metrics on spaces of finite trees
• Multidimensional scaling of measures of distance between partitions
• On clustering with chernoff-type faces
• On the computational power of pushdown automata
• Theory of equivalence relations
• Validity of clusters formed by graph-theoretic cluster methods

Cited in

(26)

• 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
• A population background for nonparametric density-based clustering
• Lattice-based similarity measures between ordered trees
• Consensus system for solving conflicts in distributed systems
• Distribution and asymptotic behavior of the phylogenetic transfer distance
• Transfer distance between partitions
• A METHOD FOR TEMPORAL KNOWLEDGE INTEGRATION USING INDETERMINATE MODEL OF TIME
• Comparison of algorithms in graph partitioning
• Geometry of graph partitions via optimal transport
• Certain calculational aspects of the clusterization problem
• Clustering and isolation in the consensus problem for partitions
• The role of complexity in comparing classifications
• A distributional framework for evaluation, comparison and uncertainty quantification in soft clustering
• On the metrization of the infinite partition lattice
• A distributional approach for soft clustering comparison and evaluation
• An efficient algorithm for computing the distance between close partitions
• A general framework for evaluating and comparing soft clusterings
• 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

This page was built for publication: The complexity of computing metric distances between partitions

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