A Spectral Algorithm for Seriation and the Consecutive Ones Problem
From MaRDI portal
Publication:4210149
DOI10.1137/S0097539795285771zbMath0930.05064OpenAlexW2006935644MaRDI QIDQ4210149
Erik G. Boman, Jonathan E. Atkins, Bruce A. Hendrickson
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539795285771
Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Positive matrices and their generalizations; cones of matrices (15B48)
Related Items (41)
A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Three conjectures of Ostrander on digraph Laplacian eigenvectors ⋮ Uniform embeddings for Robinson similarity matrices ⋮ Reconstruction of line-embeddings of graphons ⋮ Graphs, Vectors, and Matrices ⋮ Convex Relaxations for Permutation Problems ⋮ Two improved algorithms for envelope and wavefront reduction ⋮ Analysis and applications of spectral properties of grounded Laplacian matrices for directed networks ⋮ Heuristic methods to consecutive block minimization ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ The seriation problem in the presence of a double Fiedler value ⋮ Heat kernel embeddings, differential geometry and graph structure ⋮ Localization in 1D non-parametric latent space models from pairwise affinities ⋮ Modules in Robinson Spaces ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Estimation of Monge matrices ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Optimal rates of statistical seriation ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Continuation methods for approximate large scale object sequencing ⋮ Graph spectral image smoothing using the heat kernel ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ Regime switching model estimation: spectral clustering hidden Markov model ⋮ An experimental comparison of seriation methods for one-mode two-way data ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ The perturbed laplacian matrix of a graph ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Graph characteristics from the heat kernel trace ⋮ The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Recovering the structure of random linear graphs ⋮ On Physical Mapping and the consecutive ones property for sparse matrices ⋮ Discovering bands from graphs ⋮ Experiments on the minimum linear arrangement problem ⋮ A GRAPH BASED DAVIDSON ALGORITHM FOR THE GRAPH PARTITIONING PROBLEM ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Polynomial-time local-improvement algorithm for consecutive block minimization ⋮ An Optimal Algorithm for Strict Circular Seriation ⋮ Minimising the number of gap-zeros in binary matrices ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
This page was built for publication: A Spectral Algorithm for Seriation and the Consecutive Ones Problem
