*Result*: Extending Robinson spaces: Complexity and algorithmic solutions for non-symmetric dissimilarity spaces.
Title:
Extending Robinson spaces: Complexity and algorithmic solutions for non-symmetric dissimilarity spaces.
Authors:
Brucker, François1,2 (AUTHOR), Préa, Pascal1,2 (AUTHOR), Thraves Caro, Christopher1,3 (AUTHOR) cthraves@udec.cl
Source:
Discrete Applied Mathematics. May2026, Vol. 385, p306-317. 12p.
Subject Terms:
Database:
Academic Search Index
*Further Information*
*In this work, we extend the concept of Robinson spaces to asymmetric dissimilarities, enhancing their applicability in the representation and analysis of complex data. Within this generalized framework, we introduce two different problems that extend the classical seriation problem: an optimization problem and a decision problem. We establish that these problems are NP-hard and NP-complete, respectively. Despite these complexity results, we identify several nontrivial instances where these problems can be solved in polynomial time, providing valuable insights into their tractability. [ABSTRACT FROM AUTHOR]*