{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T06:53:21Z","timestamp":1742972001698,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18173-8_24","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"325-338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Lex-BFS-Based Recognition Algorithm for Robinsonian Matrices"],"prefix":"10.1007","author":[{"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Seminaroti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/S0097539795285771","volume":"28","author":"JE Atkins","year":"1998","unstructured":"Atkins, J.E., Boman, E.G., Hendrickson, B.: A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing 28, 297\u2013310 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/S1571-0653(05)80014-9","volume":"3","author":"HL Bodlaender","year":"1999","unstructured":"Bodlaender, H.L., Kloks, T., Niedermeier, R.: SIMPLE MAX-CUT for unit interval graphs and graphs with few $$P4$$s. Electronic Notes in Discrete Mathematics 3, 19\u201326 (1999)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"3","key":"24_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13(3), 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"24_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s003579900015","volume":"14","author":"V Chepoi","year":"1997","unstructured":"Chepoi, V., Fichet, B.: Recognition of Robinsonian dissimilarities. Journal of Classification 14(2), 311\u2013325 (1997)","journal-title":"Journal of Classification"},{"issue":"4","key":"24_CR5","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00453-009-9319-y","volume":"59","author":"V Chepoi","year":"2011","unstructured":"Chepoi, V., Seston, M.: Seriation in the presence of errors: A factor 16 approximation algorithm for $$l_\\infty $$-fitting Robinson structures to distances. Algorithmica 59(4), 521\u2013568 (2011)","journal-title":"Algorithmica"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11821069_24","volume-title":"Mathematical Foundations of Computer Science 2006","author":"J Cohen","year":"2006","unstructured":"Cohen, J., Fomin, F.V., Heggernes, P., Kratsch, D., Kucherov, G.: Optimal linear arrangement of interval graphs. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 267\u2013279. Springer, Heidelberg (2006)"},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG Corneil","year":"2004","unstructured":"Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Applied Mathematics 138(3), 371\u2013379 (2004)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"24_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Information Processing Letters 55(2), 99\u2013104 (1995)","journal-title":"Information Processing Letters"},{"key":"24_CR9","unstructured":"Crescenzi, P., Corneil, D.G., Dusart, J., Habib, M.: New trends for graph search. In: PRIMA Conference in Shanghai, June 2013. http:\/\/math.sjtu.edu.cn\/conference\/Bannai\/2013\/data\/20130629B\/slides1.pdf"},{"issue":"2","key":"24_CR10","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390\u2013403 (1996)","journal-title":"SIAM J. Comput."},{"key":"24_CR11","first-page":"27","volume":"98","author":"M Dom","year":"2009","unstructured":"Dom, M.: Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science 98, 27\u201359 (2009)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"24_CR12","unstructured":"Fogel, F., Jenatton, R., Bach, F., d\u2019Aspremont, A.: Convex relaxations for permutation problems. In: Advances in Neural Information Processing Systems, pp. 1016\u20131024 (2013)"},{"issue":"3","key":"24_CR13","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15(3), 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"issue":"12","key":"24_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation interval graph recognition and consecutive ones testing. Theoretical Computer Science 234(12), 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"24_CR15","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/S0895480103430259","volume":"18","author":"P Hell","year":"2005","unstructured":"Hell, P., Huang, J.: Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs. SIAM J. Discret. Math. 18(3), 554\u2013570 (2005)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"24_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0097539700372216","volume":"31","author":"P Hell","year":"2002","unstructured":"Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31(1), 289\u2013305 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"24_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.orl.2014.12.009","volume":"43","author":"M Laurent","year":"2015","unstructured":"Laurent, M., Seminaroti, M.: The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Operations Research Letters 43(1), 103\u2013109 (2015)","journal-title":"Operations Research Letters"},{"issue":"2","key":"24_CR18","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1002\/sam.10071","volume":"3","author":"I Liiv","year":"2010","unstructured":"Liiv, I.: Seriation and matrix reordering methods: An historical overview. Statistical Analysis and Data Mining 3(2), 70\u201391 (2010)","journal-title":"Statistical Analysis and Data Mining"},{"issue":"7","key":"24_CR19","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Computers & Mathematics with Applications 25(7), 15\u201325 (1993)","journal-title":"Computers & Mathematics with Applications"},{"issue":"2","key":"24_CR20","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0890-5401(91)90045-4","volume":"95","author":"R Mahesh","year":"1991","unstructured":"Mahesh, R., Rangan, C.P., Srinivasan, A.: On finding the minimum bandwidth of interval graphs. Information and Computation 95(2), 218\u2013224 (1991)","journal-title":"Information and Computation"},{"key":"24_CR21","series-title":"Biomathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69280-2","volume-title":"Graphs and genes","author":"BG Mirkin","year":"1984","unstructured":"Mirkin, B.G., Rodin, S.N.: Graphs and genes. Biomathematics. Springer, Heidelberg (1984)"},{"key":"24_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00357-014-9152-0","volume":"31","author":"P Pr\u00e9a","year":"2014","unstructured":"Pr\u00e9a, P., Fortin, D.: An optimal algorithm to recognize Robinsonian dissimilarities. Journal of Classification 31, 1\u201335 (2014)","journal-title":"Journal of Classification"},{"key":"24_CR23","first-page":"139","volume-title":"Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Graph Theory Conference","author":"FS Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Graph Theory Conference, pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Roberts, F.S.: Graph theory and its applications to problems of society. Society for Industrial and Applied Mathematics (1978)","DOI":"10.1137\/1.9781611970401"},{"issue":"4","key":"24_CR25","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS Robinson","year":"1951","unstructured":"Robinson, W.S.: A method for chronologically ordering archaeological deposits. American Antiquity 16(4), 293\u2013301 (1951)","journal-title":"American Antiquity"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Rose, D.J., Tarjan, R.E.: Algorithmic aspects of vertex elimination. In: Proceedings of Seventh Annual ACM Symposium on Theory of Computing, STOC 1975, New York, NY, USA, pp. 245\u2013254. ACM (1975)","DOI":"10.1145\/800116.803775"},{"key":"24_CR27","unstructured":"Seston, M.: Dissimilarit\u00e9s de Robinson: algorithmes de reconnaissance et d\u2019approximation. Ph.D. thesis, Universit\u00e9 de la M\u00e9diterran\u00e9e (2008)"},{"key":"24_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/3-540-54891-2_22","volume-title":"Computational Geometry - Methods, Algorithms and Applications","author":"K Simon","year":"1991","unstructured":"Simon, K.: A new simple linear algorithm to recognize interval graphs. In: Bieri, H., Noltemeier, H. (eds.) CG-WS 1991. LNCS, vol. 553, pp. 289\u2013308. Springer, Heidelberg (1991)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,9]],"date-time":"2024-06-09T00:28:45Z","timestamp":1717892925000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}