Similarity-first search: a new algorithm with application to Robinsonian matrix recognition

DOI10.1137/16M1056791MaRDI QIDQ5351862zbMATH OpenFDO

Authors 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

zbMATH Keywords

LBFSLex-BFSpartition refinementRobinson dissimilarityseriationsimilarity search

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and it exploits new insight on the combinatorial structure of Robinsonian matrices. For an $nimesn$ nonnegative matrix with $m$ nonzero entries, it terminates in $n-1$ SFS sweeps, with overall running time $O(n^2+nmlogn)$.

Recommendations

• Robinsonian matrices: recognition challenges
• A structural characterization for certifying Robinsonian matrices
• An optimal algorithm to recognize Robinsonian dissimilarities

Cites work

• A new LBFS-based algorithm for cocomparability graph recognition
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A spectral algorithm for envelope reduction of sparse matrices
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A tie-break model for graph search
• An optimal algorithm to recognize Robinsonian dissimilarities
• Convex relaxations for permutation problems
• scientific article; zbMATH DE number 3843553 (Why is no real title available?)
• scientific article; zbMATH DE number 176590 (Why is no real title available?)
• scientific article; zbMATH DE number 3593613 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On end-vertices of lexicographic breadth first searches
• Optimal greedy algorithms for indifference graphs
• Recognition of Robinsonian dissimilarities
• Seriation and matrix reordering methods: An historical overview
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• Three Partition Refinement Algorithms

Cited in

(15)

• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• The weighted sitting closer to friends than enemies problem in the line
• Reconstruction of line-embeddings of graphons
• Perfect elimination orderings for symmetric matrices
• Robinsonian matrices: recognition challenges
• The seriation problem in the presence of a double Fiedler value
• An Optimal Algorithm for Strict Circular Seriation
• A structural characterization for certifying Robinsonian matrices
• An optimization parameter for seriation of noisy data
• A Simple and Optimal Algorithm for Strict Circular Seriation
• Modules in Robinson Spaces
• Recognising permuted Demidenko matrices
• Two simple but efficient algorithms to recognize Robinson dissimilarities
• \texttt{PQser:} a Matlab package for spectral seriation
• Uniform embeddings for Robinson similarity matrices

Describes a project that uses

Uses Software

• seriation

This page was built for publication: Similarity-first search: a new algorithm with application to Robinsonian matrix recognition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351862)