A structural characterization for certifying Robinsonian matrices

MaRDI QIDQ529005zbMATH OpenFDO

Authors Monique Laurent, Matteo Seminaroti, Shin-Ichi Tanigawa

Publication date 18 May 2017

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

Full work available at URL https://arxiv.org/abs/1701.00806, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p21

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

zbMATH Keywords

asteroidal tripleRobinson matrixRobinson orderingseriationunit interval graph

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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

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

Cites work

• 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
• 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?)
• 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 node-deletion problem for hereditary properties is NP-complete
• The Roberts characterization of proper and unit interval graphs

Cited in

(13)

• The weighted sitting closer to friends than enemies problem in the line
• Cut norm discontinuity of triangular truncation of graphons
• Perfect elimination orderings for symmetric matrices
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• scientific article; zbMATH DE number 6612007 (Why is no real title available?)
• Robinson Cubes
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• scientific article; zbMATH DE number 6401305 (Why is no real title available?)
• Graph sequences sampled from Robinson 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
• Forbidden patterns in temporal graphs resulting from encounters in a corridor

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)