×

A structural characterization for certifying Robinsonian matrices. (English) Zbl 1361.05110

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.

MSC:

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

References:

[1] M.J. Brusco and S. Stahl. Branch-and-Bound Applications in Combinatorial Data Analysis. Statistics and Computing. Springer New York, 2005. · Zbl 1093.62006
[2] V. Chepoi and B. Fichet. Recognition of Robinsonian dissimilarities. Journal of Classification, 14(2):311-325, 1997. · Zbl 0905.92036
[3] D.G. Corneil. A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Applied Mathematics, 138(3):371-379, 2004. the electronic journal of combinatorics 24(2) (2017), #P2.2120 · Zbl 1042.05067
[4] D.G. Corneil, H. Kim, S. Natarajan, S. Olariu, and A.P. Sprague. Simple linear time recognition of unit interval graphs. Information Processing Letters, 55(2):99-104, 1995. · Zbl 0875.68690
[5] D.G. Corneil, S. Olariu, and L. Stewart. The ultimate interval graph recognition algorithm?In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’98, pages 175-180. Society for Industrial and Applied Mathematics, 1998. · Zbl 0930.68105
[6] C. Ding and X. He. Linearized cluster assignment via spectral ordering. In Proceedings of the 21st International Conference on Machine learning, ICML ’04. ACM Press, 2004.
[7] M.L. Fredman and L. Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21:618-628, 1998. · Zbl 0864.68038
[8] F. Gardi. The Roberts characterization of proper and unit interval graphs. Discrete Mathematics, 307(22):2906-2908, 2007. · Zbl 1126.05084
[9] V. Gurvich and L. Khachiyan. On generating the irredundant conjunctive and disjunctive normal forms of monotone boolean functions. Discrete Applied Mathematics, 96-97:363-373, 1999. · Zbl 0953.06013
[10] M.T. Hajiaghayi and Y. Ganjali. A note on the consecutive ones submatrix problem. Information Processing Letters, 83(3):163-166, 2002. · Zbl 1043.68064
[11] T.C. Havens and J.C. Bezdek. An efficient formulation of the improved visual assessment of cluster tendency (iVAT) algorithm. IEEE Transactions on Knowledge and Data Engineering, 24(5):813-822, 2012.
[12] L. Hubert, P. Arabie, and J. Meulman. Combinatorial Data Analysis. Society for Industrial and Applied Mathematics, 2001. · Zbl 0999.90047
[13] D.G. Kendall. Incidence matrices, interval graphs and seriation in archeology. Pacific Journal of Mathematics, 28(3):565-570, 1969. · Zbl 0185.03301
[14] M. Laurent and M. Seminaroti. A Lex-BFS-based recognition algorithm for Robinsonian matrices. Discrete Applied Mathematics, 222:151-165, 2017. · Zbl 1396.05051
[15] M. Laurent and M. Seminaroti. Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition.arXiv:1601.03521, 2016. To appear in SIAM Journal of Discrete Mathematics. · Zbl 1369.05152
[16] C. G. Lekkerkerker and J. C. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51(1):45-64, 1962. · Zbl 0105.17501
[17] J.M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. · Zbl 0436.68029
[18] I. Liiv. Seriation and matrix reordering methods: An historical overview. Statistical Analysis and Data Mining, 3(2):70-91, 2010. · Zbl 07260234
[19] P.J. Looges and S. Olariu. Optimal greedy algorithms for indifference graphs. Computers & Mathematics with Applications, 25(7):15-25, 1993. the electronic journal of combinatorics 24(2) (2017), #P2.2121 · Zbl 0794.68115
[20] B.G. Mirkin and S.N. Rodin. Graphs and Genes. Biomathematics. Springer, 1984. · Zbl 0531.92013
[21] W.M.F. Petrie. Sequences in prehistoric remains. Journal of the Anthropological Institute of Great Britain and Ireland, 29(3-4):295-301, 1899.
[22] P. Pr´ea and D. Fortin. An optimal algorithm to recognize Robinsonian dissimilarities. Journal of Classification, 31:1-35, 2014. · Zbl 1360.68887
[23] F.S. Roberts. Indifference graphs. In Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Graph Theory Conference, pages 139-146. Academic Press, 1969. · Zbl 0193.24205
[24] W.S. Robinson. A method for chronologically ordering archaeological deposits. American Antiquity, 16(4):293-301, 1951.
[25] Y.-J. Tien, T.-S. Lee, H.-M. Wu, and C.-H. Chen.Methods for simultaneously identifying coherent local clusters with smooth global patterns in gene expression profiles. BMC Bioinformatics, 9(1):1-16, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.