Back to Search
Start Over
MODULES IN ROBINSON SPACES.
- Source :
- SIAM Journal on Discrete Mathematics; 2024, Vol. 38 Issue 1, p190-224, 35p
- Publication Year :
- 2024
-
Abstract
- Robinson space is a dissimilarity space (X, d) (i.e., a set X of size n and a dissimilarity d on X) for which there exists a total order < on X such that x < y < z implies that d(x, z) \geq max\{ d(x, y), d(y, z)\}. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of (X, d) (generalizing the notion of a module in graph theory) is a subset M of X which is not distinguishable from the outside of M; i.e., the distance from any point of X \setminus M to all points of M is the same. If p is any point of X, then \{ p\}, and the maximal-by-inclusion mmodules of (X, d) not containing p define a partition of X, called the copoint partition. In this paper, we investigate the structure of mmodules in Robinson spaces and use it and the copoint partition to design a simple and practical divide-and-conquer algorithm for recognition of Robinson spaces in optimal O(n²) time. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPH theory
LINEAR orderings
PARTITIONS (Mathematics)
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 38
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 177075443
- Full Text :
- https://doi.org/10.1137/22M1494348