论文标题
在有双重FIEDLER值的情况下的序列问题
The seriation problem in the presence of a double Fiedler value
论文作者
论文摘要
序列化是一个问题，它是寻求一组单元的最佳枚举顺序，其相互关系由两部分图描述，即，该图的节点在两组中被分配为两组，而ARC仅在不同组中连接节点。 Atkins等人开发了一种基于与该问题相关的Laplacian矩阵的Fiedler Vector的光谱序列化算法，这是在假设Fiedler值很简单的假设下。在本文中，我们分析了Laplacian的Fiedler值并不简单的情况，请讨论其对可允许解决方案集的影响，并研究实际执行计算的可能方法。示例和数值实验说明了所提出方法的有效性。
Seriation is a problem consisting of seeking the best enumeration order of a set of units whose interrelationship is described by a bipartite graph, that is, a graph whose nodes are partitioned in two sets and arcs only connect nodes in different groups. An algorithm for spectral seriation based on the use of the Fiedler vector of the Laplacian matrix associated to the problem was developed by Atkins et al., under the assumption that the Fiedler value is simple. In this paper, we analyze the case in which the Fiedler value of the Laplacian is not simple, discuss its effect on the set of the admissible solutions, and study possible approaches to actually perform the computation. Examples and numerical experiments illustrate the effectiveness of the proposed methods.
