A structural characterization for certifying Robinsonian matrices

zbMATH Open1361.05110arXiv1701.00806MaRDI QIDQ529005FDOQ529005

Monique Laurent, Shin-Ichi Tanigawa, Matteo Seminaroti

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A Lex-BFS-based recognition algorithm for Robinsonian matrices
• A Lex-BFS-based recognition algorithm for Robinsonian matrices
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• Robinsonian matrices: recognition challenges
• Perfect elimination orderings for symmetric matrices

zbMATH Keywords

seriationunit interval graphasteroidal tripleRobinson matrixRobinson ordering

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Clustering in the social and behavioral sciences (91C20) Structural characterization of families of graphs (05C75) Special matrices (15B99)

Cites Work

• The node-deletion problem for hereditary properties is NP-complete
• Recognition of Robinsonian dissimilarities
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Optimal greedy algorithms for indifference graphs
• Incidence matrices, interval graphs and seriation in archeology
• An optimal algorithm to recognize Robinsonian dissimilarities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• Combinatorial data analysis. Optimization by dynamic programming
• Representation of a finite graph by a set of intervals on the real line
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Title not available (Why is that?)
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Title not available (Why is that?)
• The Roberts characterization of proper and unit interval graphs
• Seriation and matrix reordering methods: An historical overview
• A Lex-BFS-based recognition algorithm for Robinsonian matrices
• A note on the consecutive ones submatrix problem.
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition

Cited In (10)

• The weighted sitting closer to friends than enemies problem in the line
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Title not available (Why is that?)
• Graph sequences sampled from Robinson graphons
• Perfect elimination orderings for symmetric matrices
• Title not available (Why is that?)
• Cut norm discontinuity of triangular truncation of graphons
• Modules in Robinson Spaces
• Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
• Two simple but efficient algorithms to recognize Robinson dissimilarities

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)