2022/04/07 by Anna Concas, Caterina Fenu, Concas, Anna +5 · 1 citation
Computer Science · Engineering · Mathematics · #05C82 #65F15 #65F50 #91D30 #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2204.03362
openalex publication_date 2022/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.