A Spectral Algorithm for Seriation and the Consecutive Ones Problem
From MaRDI portal
Publication:4210149
DOI10.1137/S0097539795285771zbMATH Open0930.05064OpenAlexW2006935644MaRDI QIDQ4210149FDOQ4210149
Authors: Jonathan E. Atkins, E. G. Boman, 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
Recommendations
- Conley's spectral sequence via the sweeping algorithm
- A simple algorithm for the constrained sequence problems
- A spectral approach to consecutive pattern-avoiding permutations
- A generalized insertion algorithm for the seriation problem
- scientific article; zbMATH DE number 5606342
- An Optimal Algorithm for Strict Circular Seriation
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Algorithms and Computation
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- FPT algorithms for consecutive ones submatrix problems
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Analysis of algorithms and problem complexity (68Q25) Positive matrices and their generalizations; cones of matrices (15B48)
Cited In (48)
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- Uniform embeddings for Robinson similarity matrices
- Analysis and applications of spectral properties of grounded Laplacian matrices for directed networks
- A faster algorithm for finding minimum Tucker submatrices
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- On Physical Mapping and the consecutive ones property for sparse matrices
- An experimental comparison of seriation methods for one-mode two-way data
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
- Convex relaxations for permutation problems
- Two improved algorithms for envelope and wavefront reduction
- Obtaining matrices with the consecutive ones property by row deletions
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
- Localization in 1D non-parametric latent space models from pairwise affinities
- Title not available (Why is that?)
- An Optimal Algorithm for Strict Circular Seriation
- Heuristic methods to consecutive block minimization
- Minimising the number of gap-zeros in binary matrices
- Reconstruction of line-embeddings of graphons
- Graphs, vectors, and matrices
- Graph characteristics from the heat kernel trace
- The perturbed laplacian matrix of a graph
- An optimization parameter for seriation of noisy data
- Discovering bands from graphs
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Modules in Robinson Spaces
- Regime switching model estimation: spectral clustering hidden Markov model
- A graph based Davidson algorithm for the graph partitioning problem
- Recovering the structure of random linear graphs
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- A generalized insertion algorithm for the seriation problem
- Experiments on the minimum linear arrangement problem
- Spectral Sequencing Based on Graph Distance
- Three conjectures of Ostrander on digraph Laplacian eigenvectors
- \texttt{PQser:} a Matlab package for spectral seriation
- Hidden Hamiltonian cycle recovery via linear programming
- Periodic reordering
- The seriation problem in the presence of a double Fiedler value
- Two simple but efficient algorithms to recognize Robinson dissimilarities
- Polynomial-time local-improvement algorithm for consecutive block minimization
- Seriation algorithms for determining the evolution of \textit{The Star Husband Tale}
- Heat kernel embeddings, differential geometry and graph structure
- Graph spectral image smoothing using the heat kernel
- Continuation methods for approximate large scale object sequencing
- Optimal rates of statistical seriation
- Estimation of Monge matrices
- Spectral reordering of a range-dependent weighted random graph
This page was built for publication: A Spectral Algorithm for Seriation and the Consecutive Ones Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210149)
