An Optimal Algorithm To Recognize Robinsonian Dissimilarities

详细信息    查看全文

• 作者：Pascal Préa (1) (3)
  Dominique Fortin (2)
  
• 关键词：Robinsonian dissimilarities ; Classification ; Seriation ; Interval graphs ; PQ ; Trees ; Consecutive One’s Property ; Partition refinement
• 刊名：Journal of Classification
• 出版年：2014
• 出版时间：October 2014
• 年：2014
• 卷：31
• 期：3
• 页码：351-385
• 全文大小：485 KB
• 参考文献：1. BARTHéLEMY, J.P., and BRUCKER, F. (2003), “NP-Hard Approximation Problems in Overlapping Clustering- / Journal of Classification, 18, 159-183.
  2. BARTHéLEMY, J.P., and GUéNOCHE, A. (1991), / Trees and Proximity Representations, New York: J. Wiley & Sons.
  3. BENZER, S. (1962), “The Fine Structure of the Gene- / Scientific American, 206 (1), 70-84.
  4. BERRY, M.W., HENDRICKSON, B., and RAGHAVAN, P. (1996), “Sparse Matrix Reordering Schemes for Browsing Hypertext- in / The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, eds. J. Renegar, M. Shub and S. Smale, American Mathematical Society, pp. 99-123.
  5. BONEVA, L. (1980), “Seriation with Applications in Philology- in / Mathematical Statistics, eds. R. Bartoszynski, J. Koronacki and R. Zielinski, Warsaw: PWN Polish Scientific Publishers, pp. 73-82.
  6. BOOTH, K.S. (1975), / PQ-Tree Algorithms, Ph.D. Thesis, University of California.
  7. BOOTH, K.S., and LUEKER, G.S. (1976), “Testing for the Consecutive Ones Property, Interval Graphs and Graph Planarity Using PQ-Tree Algorithm- / Journal of Computer and System Sciences, 13, 335-379. dx.doi.org/10.1016/S0022-0000(76)80045-1" target="_blank" title="It opens in new window">CrossRef
  8. BRUSCO, M.J. (2002), “A Branch-and-Bound Algorithm for Fitting Anti-Robinson Structures to Symmetric Dissimilarity Matrices- / Psychometrika, 67, 459-471. dx.doi.org/10.1007/BF02294996" target="_blank" title="It opens in new window">CrossRef
  9. CARAUX, G., and PINLOCHE, S. (2005), “PermutMatrix: A Graphical Environment to Arrange Gene Expression Profiles in Optimal Linear Order- / Bioinformatics, 21, 1280-1281. dx.doi.org/10.1093/bioinformatics/bti141" target="_blank" title="It opens in new window">CrossRef
  10. CHEN, C.H., HWU, H.G., JANG, W.J., KAO, C.H., TIEN, Y.J., TZENG, S., and WU, H.M. (2004), “Matrix Visualisation and Information Mining- in / Proceedings in Computational Statistics, COMPSTAT-004, Springer, pp. 85-100.
  11. CHEPOI, V., and FICHET, B. (1997), “Recognition of Robinsonian Dissimilarities- / Journal of Classification, 14, 311-325. dx.doi.org/10.1007/s003579900015" target="_blank" title="It opens in new window">CrossRef
  12. 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, 279-296. dx.doi.org/10.1007/s00357-009-9041-0" target="_blank" title="It opens in new window">CrossRef
  13. CHEPOI, V., and SESTON, M. (2011), “Seriation in the Presence of Errors: A Factor 16 Approximation Algorithm for l?Fitting Robinson Structures to Distances- / Algorithmica, 59, 521-568. dx.doi.org/10.1007/s00453-009-9319-y" target="_blank" title="It opens in new window">CrossRef
  14. CRITCHLEY, F., and FICHET, B. (1994), “The Partial Order by Inclusion of the Principal Classes of Dissimilarities on a Finite Set, and Some of Their Basic Properties- in / Classification and Dissimilarity Analysis, Lecture Notes in Statistics, ed. B. Van Cutsem, New York: Springer Verlag, pp. 5-65.
  15. DIDAY, E. (1986), “Orders and Overlapping Clusters by Pyramids- in / Multidimensionnal Data Analysis, ed. J. de Leeuw, W. Heiser, J. Meulman and F. Critchley, Leiden: DSWO Press, pp. 201-234.
  16. DURAND, C., and FICHET, B. (1988), “One-to-One Correspondences in Pyramidal Representation: An Unified Approach- in / Classification and Related Methods of Data Analysis, ed. H.H. Bock, Amsterdam: North-Holland, pp. 85-90.
  17. FULKERSON, D.R., and GROSSM, O.A. (1965), “Incidence Matrices and Interval Graphs- / Pacific Journal of Mathematics, 15, 835-855. dx.doi.org/10.2140/pjm.1965.15.835" target="_blank" title="It opens in new window">CrossRef
  18. GILMORE, P.C., and HOFFMAN, A.J. (1964), “A Characterization of Comparability Graphs and of Interval Graphs- / Canadian Journal of Mathematics, 16, 539-548. dx.doi.org/10.4153/CJM-1964-055-5" target="_blank" title="It opens in new window">CrossRef
  19. GOLUMBIC, M.C. (1980), / Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press.
  20. 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, 59-84. dx.doi.org/10.1016/S0304-3975(97)00241-7" target="_blank" title="It opens in new window">CrossRef
  21. HALPERIN, D. (1994), “Musical Chronology by Seriation- / Computer and the Humanities, 28, 13-18.
  22. HEUN, V. (2008), “Analysis of a Modifica
• 作者单位：Pascal Préa (1) (3)
  Dominique Fortin (2)
  
  1. école Centrale Marseille, Marseille, France
  3. LIF, Laboratoire d’Informatique Fondamentale de Marseille CNRS UMR 7279, école Centrale Marseille, Technop?le de Chateau-Gombert, 38, rue Joliot Curie, 13451, Marseille Cédex 20, France
  2. INRIA, Paris, France
  
• ISSN：1432-1343

文摘

A dissimilarity D on a finite set S is said to be Robinsonian if S can be totally ordered in such a way that, for every i j k, D (i, j) ?D (i, k) and D (j, k) ?D (i, k). Intuitively, D is Robinsonian if S can be represented by points on a line. Recognizing Robinsonian dissimilarities has many applications in seriation and classification. In this paper, we present an optimal O (n 2) algorithm to recognize Robinsonian dissimilarities, where n is the cardinal of S. Our result improves the already known algorithms.