A Lex-BFS-based recognition algorithm for Robinsonian matrices

DOI10.1016/j.dam.2017.01.027zbMath1396.05051arXiv1504.06586OpenAlexW2590904539MaRDI QIDQ1786881

Matteo Seminaroti, Monique Laurent

Publication date: 25 September 2018

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.06586

zbMATH Keywords

seriationpartition refinementunit interval graphRobinson (dis)similarityLex-BFSstraight enumeration

Mathematics Subject Classification ID

Measures of association (correlation, canonical correlation, etc.) (62H20) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10) Enumeration in graph theory (05C30) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Uniform embeddings for Robinson similarity matrices ⋮ Robinsonian matrices: recognition challenges ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ 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 ⋮ A structural characterization for certifying Robinsonian matrices ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ The weighted sitting closer to friends than enemies problem in the line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm to recognize Robinsonian dissimilarities
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• An optimal greedy heuristic to color interval graphs
• On finding the minimum bandwidth of interval graphs
• 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
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• 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
• Incidence matrices and interval graphs
• On the compatibility between a graph and a simple order
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Seriation and matrix reordering methods: An historical overview
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Optimal Linear Arrangement of Interval Graphs

This page was built for publication: A Lex-BFS-based recognition algorithm for Robinsonian matrices