Mikhael Carmona

dblp:317/0623 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2025 Modules and PQ-trees in Robinson spaces
Mikhael Carmona, Victor Chepoi, Guyslain Naves, Pascal Préa
Inf. Comput.1
2024 Modules in Robinson Spaces
abstract
Abstract. A Robinson space is a dissimilarity space [Formula: see text] (i.e., a set [Formula: see text] of size [Formula: see text] and a dissimilarity [Formula: see text] on [Formula: see text]) for which there exists a total order [Formula: see text] on [Formula: see text] such that [Formula: see text] implies that [Formula: see text]. Recognizing if a dissimilarity space is Robinson has numerous applications in seriation and classification. An mmodule of [Formula: see text] (generalizing the notion of a module in graph theory) is a subset [Formula: see text] of [Formula: see text] which is not distinguishable from the outside of [Formula: see text]; i.e., the distance from any point of [Formula: see text] to all points of [Formula: see text] is the same. If [Formula: see text] is any point of [Formula: see text], then [Formula: see text], and the maximal-by-inclusion mmodules of [Formula: see text] not containing [Formula: see text] define a partition of [Formula: see text], 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 [Formula: see text] time.
Mikhael Carmona, Victor Chepoi, Guyslain Naves, Pascal Préa
SIAM J. Discret. Math.1