论文标题
罗宾逊空间中的模块
Modules in Robinson Spaces
论文作者
论文摘要
鲁滨逊空间是一个不同的空间$（x，d）$（即$ n $的$ x $和$ x $上的差异$ d $），在$ x $上存在总订单$ <$ <y <z $，因此$ x <y <z $暗示$ x <z $ d（x，x，x，x，z）认识到差异空间是鲁滨逊在序列和分类中都有许多应用。 $（x，d）$的mmodule（概括图理论中的模块的概念）是$ x $的子集$ m $，与$ m $的外部没有区别，即，距$ x \ setminus m $的任何点的距离到$ m $的所有点是相同的。如果$ p $是$ x $的任何点，则$ \ {p \} $和不包含包含$ p $的$（x，d）$的包含mmodules的最大值定义了$ x $的分区，称为Copoint分区。在本文中，我们研究了鲁滨逊空间中的mmodules的结构，并使用它和Copoint分区来设计一种简单且实用的分界线和争议算法，以识别最佳$ O（N^2）$时间的Robinson空间。
A 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)\ge \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^2)$ time.
