Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
From MaRDI portal
Publication:5351862
DOI10.1137/16M1056791zbMath1369.05152arXiv1601.03521MaRDI QIDQ5351862
Matteo Seminaroti, Monique Laurent
Publication date: 31 August 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.03521
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (13)
A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Uniform embeddings for Robinson similarity matrices ⋮ Reconstruction of line-embeddings of graphons ⋮ Robinsonian matrices: recognition challenges ⋮ Perfect elimination orderings for symmetric matrices ⋮ The seriation problem in the presence of a double Fiedler value ⋮ Modules in Robinson Spaces ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ A structural characterization for certifying Robinsonian matrices ⋮ The weighted sitting closer to friends than enemies problem in the line ⋮ An Optimal Algorithm for Strict Circular Seriation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- A new LBFS-based algorithm for cocomparability graph recognition
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Simple linear time recognition of unit interval graphs
- A tie-break model for graph search
- On end-vertices of lexicographic breadth first searches
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognition of Robinsonian dissimilarities
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- A Lex-BFS-based recognition algorithm for Robinsonian matrices
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Optimal greedy algorithms for indifference graphs
- The LBFS Structure and Recognition of Interval Graphs
- Convex Relaxations for Permutation Problems
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- Three Partition Refinement Algorithms
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A spectral algorithm for envelope reduction of sparse matrices
- Seriation and matrix reordering methods: An historical overview
This page was built for publication: Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
