The complexity of computing metric distances between partitions
From MaRDI portal
Publication:1170849
DOI10.1016/0165-4896(81)90042-1zbMath0497.62049OpenAlexW2017930713MaRDI 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
latticealgorithmclusteringcomplexity of computing metric distancesgraph-theoretic representationssimilarity of partitions
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (25)
Comparison of algorithms in graph partitioning ⋮ 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 ⋮ An efficient algorithm for computing the distance between close partitions ⋮ 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 ⋮ Transfer distance between partitions ⋮ Geometry of Graph Partitions via Optimal Transport ⋮ Two local dissimilarity measures for weighted graphs with application to protein interaction networks ⋮ Consensus of partitions: a constructive approach ⋮ Transfer distance between partitions and search of dense zones in graphs ⋮ Certain calculational aspects of the clusterization problem ⋮ Clustering and isolation in the consensus problem for partitions ⋮ A METHOD FOR TEMPORAL KNOWLEDGE INTEGRATION USING INDETERMINATE MODEL OF TIME ⋮ The role of complexity in comparing classifications ⋮ SEP/COP: an efficient method to find the best partition in hierarchical clustering based on a new cluster validity index ⋮ A population background for nonparametric density-based clustering ⋮ Distribution and asymptotic behavior of the phylogenetic transfer distance ⋮ Lattice-based similarity measures between ordered trees ⋮ Approximating minimum-length-sequence metrics: A cautionary note ⋮ Properties of Levenshtein metrics on sequences ⋮ A computationally efficient approximation to the nearest neighbor interchange metric ⋮ Consensus system for solving conflicts in distributed systems
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
This page was built for publication: The complexity of computing metric distances between partitions
