Abstract
Ultrametric inequality is involved in different operations on (dis)similarity matrices. Its coupling with a compatible ordering leads to nice interpretations in seriation problems. We accurately review the interval graph recognition problem for its tight connection with recognizing a dense Robinsonian dissimilarity (precisely, in the anti-ultrametric case). Since real life matrices are prone to errors or missing entries, we address the sparse case and make progress towards recognizing sparse Robinsonian dissimilarities with lexicographic breadth first search. The ultrametric inequality is considered from the same graph point of view and the intimate connection between cocomparability graph and dense Robinsonian similarity is established. The current trend in recognizing special graph structures is examined in regard to multiple lexicographic search sweeps. Teaching examples illustrate the issues addressed for both dense and sparse symmetric matrices.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
AVIS, D., and FUKUDA, K. (1992), “A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra”, Discrete and Computational Geometry, 8(3), 295–313.
BERRY, A., and BORDAT, J.-P. (1998), “Separability Generalizes Dirac’s Theorem”, Discrete and Applied Mathematics, 84(1-3), 43–53.
BOOTH, K.S., and LUEKER, G.S. (1976), “Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms”, Journal of Computer and System Sciences, 13(3), 335–379.
BURKARD, R.E., ÇELA, E., ROTE, G., and WOEGINGER, G.J. (1998), “The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases”, Mathematical Programming, 82(1-2, Ser. B), 125–158.
ÇELA, E., DEINEKO, V.G., and WOEGINGER, G.J. (2012), “Another Well-Solvable Case of the QAP: Maximizing the Job Completion Time Variance”, Operations Research Letters, 40(5), 356–359.
CHEPOI, V., and FICHET, B. (1997), “Recognition of Robinsonian Dissimilarities”, Journal of Classification, 14(2), 311–325.
CHEPOI, V., FICHET, B., and SESTON, M. (2009), “Seriation in the Presence of Errors: NP-Hardness of l∞-Fitting Robinson Structures to Dissimilarity Matrices”, Journal of Classification, 26(3), 279–296.
CORNEIL, D.G. (2004), “A Simple 3-Sweep LBFS Algorithm for the Recognition of Unit Interval Graphs”, Discrete Applied Mathematics, 138(3), 371–379.
CORNEIL, D.G., OLARIU, S., and STEWART, L. (1999), “Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-Free Graphs”, SIAM Journal on Computing, 28(4), 1284–1297.
CORNEIL, D.G., OLARIU, S. and STEWART, L., (2009/10) “The LBFS Structure and Recognition of Interval Graphs”, SIAM Journal on Discrete Mathematics, 23(4), 1905–1953.
CORNEIL, D.G., DUSART, J., HABIB, M., MAMCARZ, A., and DE MONTGOLFIER, F. (2016), “A Tie-Break Model for Graph Search”, Discrete Applied Mathematics, 199, 89–100.
DAHLHAUS, E. (1993), “Fast Parallel Recognition of Ultrametrics and TreeMetrics”, SIAM Journal on Discrete Mathematics, 6(4), 523–532.
DIETRICH, B.L. (1990), “Monge Sequences, Antimatroids, and the Transportation Problem with Forbidden Arcs”, Linear Algebra and Its Applications, 139, 133–145.
FORTIN, D., and RUDOLF, R. (1998), “Weak Monge Arrays in Higher Dimensions”, Discrete Mathematics, 189(1-3), 105–115.
HABIB, M., MCCONNELL, R., PAUL, C., and VIENNOT, L. (2000), “Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing”, Theoretical Computer Science, 234(1-2), 59–84.
HOŞTEN, S., and MORRIS, W.D. Jr. (1999), “The Order Dimension of the Complete Graph”, Discrete Mathematics, 201(1-3), 133–139.
HUBERT, L., and ARABIE, P. (1994), “The Analysis of Proximity Matrices Through Sums of Matrices Having (Anti)-Robinson Forms”, British Journal of Mathematical and Statistical Psychology, 47, 1–40.
KLINZ, B., RUDOLF, R., and WOEGINGER, G.J. (1995), “On the Recognition of Permuted Bottleneck Monge Matrices”, Discrete Applied Mathematics, 63(1), 43–74.
KÖHLER, E., and MOUATADID, L. (2014), “Linear Time LexDFS on Cocomparability Graphs”, in Algorithm Theory—SWAT 2014, Vol. 8503, Lecture Notes in Computer Science, Springer, pp. 319–330.
LAURENT, M. (1996), “Graphic Vertices of the Metric Polytope”, Discrete Mathematics, 151(1-3), 131–153.
LAURENT, M., and SEMINAROTI, M. (2015a), A Lex-BFS-Based Recognition Algorithm for Robinsonian Matrices, Springer International Publishing, pp. 325–338.
LAURENT, M., and SEMINAROTI, M. (2015b), “The Quadratic Assignment Problem is Easy for Robinsonian Matrices with Toeplitz Structure”, Operations Research Letters, 43(1), 103–109.
LAURENT, M., and SEMINAROTI, M. (2016), “Similarity-First Search: A New Algorithm with Application To RobinsonianMatrix Recognition”, CoRR, abs/1601.03521, http://arxiv.org/abs/1601.03521.
LEKKERKERKER, C.G., and BOLAND, J.C. (1962/1963), “Representation of a Finite Graph by a Set of Intervals on the Real Line”, Fundamenta Mathematicae, 51, 45–64.
LI, P., and WU, Y. (2014), “A Four-Sweep LBFS Recognition Algorithm for Interval Graphs”, Discrete Mathematics and Theoretical Computer Science, 16(3), 23–50.
MCCONNELL, R.M., and SPINRAD, J.P. (1994), “Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs”, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), New York: ACM, pp. 536–545.
PRÉA, P., and FORTIN, D. (2014), “An Optimal Algorithm to Recognize Robinsonian Dissimilarities”, Journal of Classification, 31(3), 351–385.
ROBINSON, W. (1951), “A Method for Chronologically Ordering Archaeological Deposits”, American Antiquity, 16(4), 293–301.
RUDOLF, R., and WOEGINGER, G.J. (1995), “The Cone of Monge Matrices: Extremal Rays and Applications”, ZOR—Mathematical Methods of Operations Research, 42(2), 161–168.
TSEVENDORJ, I. (2001), “Piecewise-Convex Maximization Problems: Global Optimality Conditions”, Journal of Global Optimization, 21(1), 1–14.
XU, S.-J., LI, X., and LIANG, R. (2013), “Moplex Orderings Generated by the LexDFS Algorithm”, Discrete Applied Mathematics, 161(13-14), 2189–2195.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fortin, D. Robinsonian Matrices: Recognition Challenges. J Classif 34, 191–222 (2017). https://doi.org/10.1007/s00357-017-9230-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00357-017-9230-1