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

seriationpartition refinementsimilarity searchLBFSLex-BFSRobinson dissimilarity

Mathematics Subject Classification ID

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

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

• 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?)
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A new LBFS-based algorithm for cocomparability graph recognition
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A spectral algorithm for envelope reduction of sparse matrices
• A tie-break model for graph search
• An optimal algorithm to recognize Robinsonian dissimilarities
• Convex relaxations for permutation problems
• 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: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• 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
• 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)

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

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)