A structural characterization for certifying Robinsonian matrices
From MaRDI portal
Abstract: A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.
Recommendations
Cites work
- scientific article; zbMATH DE number 3843553 (Why is no real title available?)
- scientific article; zbMATH DE number 1303554 (Why is no real title available?)
- scientific article; zbMATH DE number 3307330 (Why is no real title available?)
- scientific article; zbMATH DE number 2231543 (Why is no real title available?)
- A note on the consecutive ones submatrix problem.
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- An optimal algorithm to recognize Robinsonian dissimilarities
- Combinatorial data analysis. Optimization by dynamic programming
- Incidence matrices, interval graphs and seriation in archeology
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Optimal greedy algorithms for indifference graphs
- Recognition of Robinsonian dissimilarities
- Representation of a finite graph by a set of intervals on the real line
- Seriation and matrix reordering methods: An historical overview
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- Simple linear time recognition of unit interval graphs
- The Roberts characterization of proper and unit interval graphs
- The node-deletion problem for hereditary properties is NP-complete
Cited in
(12)- scientific article; zbMATH DE number 6401305 (Why is no real title available?)
- Two simple but efficient algorithms to recognize Robinson dissimilarities
- Graph sequences sampled from Robinson graphons
- Cut norm discontinuity of triangular truncation of graphons
- Perfect elimination orderings for symmetric matrices
- scientific article; zbMATH DE number 6612007 (Why is no real title available?)
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- The weighted sitting closer to friends than enemies problem in the line
- Robinson Cubes
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- Modules in Robinson Spaces
This page was built for publication: A structural characterization for certifying Robinsonian matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q529005)
